LeetCode9 leetcode 15 - 3Sum https://leetcode.com/problems/3sum/ 풀이 nums[i] + nums[j] + nums[k] = 0을 만족하는 i, j, k를 찾는 문제이다. 여러 가지 풀이 방법이 있는 2 sum을 n번 돌리면 되는 것 같아 보이지만 output이 중복을 제거한 정답들의 리스트라는 점에서 제약이 생긴다. 먼저 nums를 정렬을 하고 i 0 → k를 감소 이렇게 j와 k를 좁히다가 nums[i] + nums[j.. 2020. 10. 29. leetcode 1402 - Reducing Dishes https://leetcode.com/problems/reducing-dishes/submissions/ 풀이 몇 개의 접시를 없애야 한다면 어떤 접시를 없애는 것이 좋을지 생각해보자. 당연히 satisfaction이 낮은 접시를 우선 없애는 것이 최선이다. 없앤다면 satisfaction이 낮은 접시 n개를 없애는 게 최선이고, 이다음 남은 접시의 순서를 찾는 방법은 더 쉽다. 뒤로 갈수록 가중치가 크기 때문에 오름차순으로 정렬을 하면 된다. 다시 정리해보면, 먼저 접시를 정렬한 후 앞에서부터 한 개씩 없애보면서 최고 높은 satisfaction 값을 찾으면 답이 된다. $[a_1, a_2, a_3, ...., a_n]$으로 정렬을 했을 때 가능한 정답은 다음 중에 있다. 0개 없앤 경우: $a_1 +.. 2020. 10. 15. leetcode 827 - Making A Large Island https://leetcode.com/problems/making-a-large-island/ 풀이 먼저 모든 island를 flood fill 하면서 구분 짓고 크기를 센다. 0은 경계선이고 1은 island라는 의미를 가지기 때문에 아래 코드에서는 island id는 2부터 증가하는 숫자로 구분 지었다. island를 구분 짓고 크기를 세었으면 모든 0인 부분에 대해서 1로 바꿔보고 이웃한 island의 크기를 합해본다. 4방향 이웃의 크기를 더할 때 같은 island인 경우 중복해서 더하면 안 되기 때문에 먼저 island id로 중복을 제거한다. 모든 맵을 순회 하면서 flood fill을 한번 하기 때문에 시간 복잡도는 $O(n^2)$ 이다. 코드 class Solution { public: v.. 2020. 10. 13. leetcode 85 - Maximal Rectangle https://leetcode.com/problems/maximal-rectangle/ 풀이 모든 시작, 끝에 대해 사각형을 비교해보면 $O(n^4)$만에 찾을 수 있다. 여기서 조금씩 개선해보자. matrix[i][j]가 있을 때 모든 i, j 쌍에 대해서 비교하지 말고, 아래와 같이 높이 배열을 사용하면 개선할 수 있다. height[i][j] = matrix[i][j]부터 위에(같은 열) 존재하는 연속된 1의 개수 이렇게 height[i][j]를 정의하면 모든 $n^2$개의 행의 쌍이 아닌 고정된 행에서만 비교하면 되기 때문에 $O(n^3)$만에 구할 수 있다. i는 $O(n)$으로 줄였지만 여전히 height 하나의 행에서 최대 직사각형을 찾기 위해 $O(n^2)$이 필요하다. 모든 인덱스에 대해.. 2020. 10. 13. leetcode 778 - Swim in Rising Water https://leetcode.com/problems/swim-in-rising-water/ 풀이 BFS로 현재 상태에서 갈 수 있는 다음 상태를 찾는다. 대신 최단 거리를 찾아야 하므로 현재 상태를 고를 때 모든 상태 중에 가장 좋은 상태를 뽑아야 한다. 가장 좋은 상태는 문제 정의 그대로 최소 시간이다. 이렇게 필요한 { 시간, x좌표, y좌표 } 세 가지를 가지는 set 자료구조를 사용해서 다익스트라를 사용해서 목적지까지의 최소 시간을 구할 수 있다. 모든 위치에 $n^2$에 대해서 set에 insert / erase가 필요하기 때문에 시간 복잡도는 $O(n^2 log n^2)$이다. 코드 class Solution { public: vector dir = {{0,1}, {0,-1}, {1,0}, .. 2020. 10. 7. leetcode 410 - Split Array Largest Sum https://leetcode.com/problems/split-array-largest-sum/ 풀이 입력된 리스트를 m개로 나눴을 때 sum이 가장 큰 subarray 최소화하는 문제를 한 번에 풀기는 쉽지 않다. 하지만 subarray의 sum이 k가 넘지 않도록 m개로 나눌 수 있냐는 문제는 쉽게 풀 수 있다. sum이 k가 넘지 않는 선까지 최대한 그리디 하게 묶어보면 된다. 그러면 문제를 바꿔서 모든 k에 대해 m개로 나눌 수 있는지 확인하는 방법에서 되는데, 여기서 한단계 더 나아가 파라메트릭 서치를 이용할 수 있다. 정답이 k라고 했을 때 k이하의 수에 대해서는 m개로 나눌 수 있고, k보다 큰 수에 대해서는 나눌 수 없는 특성이 있기 때문이다. 이 k를 이분 검색으로 답을 좁혀가면 된다... 2020. 10. 6. 이전 1 2 다음
