문제 https://leetcode.com/problems/spiral-matrix/ Spiral Matrix - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 재귀 형식으로 해결한 문제. 행렬을 나선형 순서로 돌아가기 위해서는 결국에는 외각을 한 바퀴 돌고 한 칸 안쪽에서 다시 한 바퀴 도는 것을 반복하게 된다. 따라서 재귀로 표현하기 적합하다. 한 칸의 외각의 범위를 표현하기 위해서는 단 두가지 점인, 왼쪽 위(left top)와 ..

문제 https://leetcode.com/problems/set-matrix-zeroes/ Set Matrix Zeroes - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 단순히 새로운 2차원 배열에 값을 복사해 넣으면서 만들면 굉장히 쉽지만 O(mn)의 공간 복잡도가 소요된다. 공간 복잡도를 최적화하는 다른 방법으로는 각 row와 column이 0으로 채워져야하는지 여부를 O(n + m) 공간으로 저장은 가능하지만, 문제에서는 i..

문제 https://leetcode.com/problems/merge-k-sorted-lists/ Merge k Sorted Lists - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Hard 대표적인 우선순위 큐 문제. 일반적인 정렬로 해결하기에는 범위가 너무 크다. 리스트의 최대 개수(k)는 10,000개, 각 리스트의 연결 노드들은 최대 500개가 될 수 있다. 모두 한꺼번에 정렬로 해결할려면 최악의 경우 5,000,000 개의 노드를 정렬..

문제 https://leetcode.com/problems/merge-two-sorted-lists/ Merge Two Sorted Lists - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Easy 정렬되어 주어지는 2가지 NodeList를 정렬된 순서로 병합하는 문제. 반복문 풀이와 재귀 풀이 두 가지를 모두 확인해보자. 반복문 풀이 반복문은 두 연결 노드의 값을 비교하여 더 작은 값을 새로운 병합 연결 노드와 연결해주자. 최종적으로는 한쪽의..

문제 https://leetcode.com/problems/non-overlapping-intervals/ Non-overlapping Intervals - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 겹치지 않는 구간들만을 남기고 만약 겹치는 구간이 있다면 최소로 제거돼야 하는 구간의 수를 구하는 문제였다. 예를 들어 [1,2] [3,4] [1,4]의 구간이 있다면 [1,4]가 나머지 두 구간을 포함하며 겹친 상태가 된다. 겹치지 ..

문제 https://leetcode.com/problems/merge-intervals/ Merge Intervals - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 이전 문제 [LeetCode] 57. Insert Interval (Java)와 거의 비슷하게 해결할 수 있지만, 추가적인 아이디어도 소개하겠다. 일단, 가장 간단한 풀이는 주어진 2차원 배열을 정렬 후에 겹치는(overlapping) 부분을 합치면 된다. 자바에서의 2..

문제 https://leetcode.com/problems/insert-interval/ Insert Interval - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium start와 end로 구성된 구간이 주어질 때, 새로운 구간의 삽입으로 변경된 구간을 반환하는 문제. 사실 주어지는 모든 구간은 겹치는(overlapping) 구간이 없이 모두 정렬되어 있지만, 주어지는 모든 구간도 겹치는 부분을 판단해 주는 문제로 풀어버렸다. 이런 풀..

문제 https://leetcode.com/problems/longest-consecutive-sequence/ Longest Consecutive Sequence - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 간단히 정렬로 해결하고 싶지만 시작 복잡도를 O(n)으로 구현해야 하는 문제. O(n)으로 구현하기 위해서는 값의 삽입, 삭제가 O(1)에 가능한 자료구조를 사용해야 한다. 가장 간단한 1차원 배열에 nums의 원소들을 저장..

문제 https://leetcode.com/problems/number-of-islands/ Number of Islands - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium DFS나 BFS로 풀 수 있는 문제로, 각 grid의 방문 여부를 저장하는 2차원 boolean 배열 visited로 간단히 구현할 수 있다. 모든 격자 중에 아직 방문하지 않고 1인 격자에서 DFS나 BFS를 실행할 때마다 Island의 count를 1씩 늘려준..

문제 https://leetcode.com/problems/pacific-atlantic-water-flow/ Pacific Atlantic Water Flow - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 난이도: Medium 처음에는 해석하는데 애를 먹었는데 height above sea level이 해발고도를 의미하는 것이었다. 태평양(Pacific)과 대서양(Atlantic)으로 둘러싸인 섬의 각 좌표의 해발고도가 주어지고 물은 같거나 낮은 곳으..