[프로그래머스] LV2 가장 큰 정사각형 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12905 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법격자의 크기가 1000 * 1000 이다.격자를 순환하며 격자의 크기를 탐색하는 방법 -> 3차원 배열로 해결할 수 있지만 10^9이므로 시간초과가 발생한다 따라서 O(n^2) 이하의 알고리즘을 사용해야한다dp를 사용해 현재 현재 정사각형의 크기를 기록하며 최대값을 비교하자현재 idx를 (r,c) 라고 할때, (r-1,c-1), (r-1,c), (r,c-1), 값과 (r,c)이 모두 1이면 한 변의 길이가 2인 정사각형이다따라서 0인경..

  • format_list_bulleted Algorithm
  • · 2024. 11. 4.
  • textsms

[프로그래머스] LV 2 테이블 해시 함수

https://school.programmers.co.kr/learn/courses/30/lessons/147354 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법data배열의 길이는 최대 2500, 각 data의 원소인 배열의 길이는 최대 500따라서 시키는대로 구현하면 된다연산에 사용되는 index와 실제 저장되는 index의 차이를 잘 생각하면된다코드import java.util.*;class Solution { public int solution(int[][] data, int col, int row_begin, int row_end) { Arrays.sort(data..

  • format_list_bulleted Algorithm
  • · 2024. 11. 4.
  • textsms

[프로그래머스] LV 3 징검다리 건너기

https://school.programmers.co.kr/learn/courses/30/lessons/64062# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr접근방법건너는 사람은 무한대, 각 돌의 내구도는 1 ~ 2억, 돌 내구도 배열의 크기는 최대 20만따라서 돌 배열을 순회하며 O(nlogm) 이하의 알고리즘으로 풀이를 해야한다한명씩 건널때 마다 돌 내구도는 -1이된다이분탐색으로 1 ~ 2억의 범위에서 적당한 사람 수 를 구하기로한다먼저 돌 내구도의 max값을 구해 이분 탐색을 구현한다건넌사람이 mid 값으로 가정하고 돌 내구도 배열을 순회한다s-m 값이 0 이하인구간이 k이상 유지된다면 해당 ..

  • format_list_bulleted Algorithm
  • · 2024. 11. 1.
  • textsms

[프로그래머스] LV 2 괄호변환

https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법결론은 문제에서 하란대로 하면된다 (근데 문제를 이해하기 힘들었다)문제의 핵심은 문자열을 받아 올바른 문자열로 바꾸는 메서드를 작성하는것이고 다음과 같은 흐름으로 구현할 수 있다입력 문자열이 비었다면 빈문자열을 반환한다입력 문자열을 u,v로 나눈다입력 문자열을 선형탐색하며 처음으로 "균형 잡힌 문자열"이 되는 구간 = u나머지 = vu 가 올바른 문자열이라면 출력 문자열에 u를 붙이고 v이를 다시 재귀로 돌린다올바르지 않다면출력 문자열..

  • format_list_bulleted Algorithm
  • · 2024. 11. 1.
  • textsms

[프로그래머스] LV 3 보석 쇼핑

https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근 방법gems 배열의 크기는 10만 이하이므로 O(n^2)은 안된다.조건에 맞는 구간을 찾는 문제이므로 투포인터 생각구간내에 모든 보석 종류가 있는지 확인해야하므로 set에 보석을 담아 보석 종류 개수 저장투포인터 구현right 포인터를 움직이며 구간을 늘린다 => map에 보석종류별로 몇개 나왔는지 저장left 포인터를 움직이는 조건: 포인터가 있는 보석이 1개 초과인 경우 움직이며 구간을 좁힌다길이 저장 조건: map 사이즈 == 보석 ..

  • format_list_bulleted Algorithm
  • · 2024. 10. 31.
  • textsms

[프로그래머스] LV 3 행렬 테두리 회전하기

https://school.programmers.co.kr/learn/courses/30/lessons/77485 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr접근 방법rows, columns가 100이하이다. O(n^2)도 무리 없이 돌아가므로 구현으로 풀었다먼저 조건에 맞는 map을 만든다각 쿼리에 맞는 회전을 수행하며 가장작은 숫자를 받아와 ansList에 담는다회전을 구현한다회전은 swap할때 처럼 tmp에 최초 원소를 담고 주어진 방향 순서대로 돌며 값을 덮어썼다.마지막에 최초원소가 가야할 자리에 tmp를 덮어썼다.코드class Solution { int n,m; int[][] ma..

  • format_list_bulleted Algorithm
  • · 2024. 10. 31.
  • textsms