문제 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)으로 둘러싸인 섬의 각 좌표의 해발고도가 주어지고 물은 같거나 낮은 곳으..

문제 https://leetcode.com/problems/course-schedule/ Course Schedule - 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 선수 과목은 방향 그래프로 나타낼 수 있다. 문제에 주어지는 것은 방향 그래프의 edge이므로 선수 과목인 b에서 a로의 간선을 저장해주는 것으로 간단히 그래프를 구현할 수 있다. 단, 아래와 같이 0과 1 과목이 서로를 선수과목으로 가지고 있다면 두 과목 모두 수강할 ..

문제 https://leetcode.com/problems/clone-graph/ Clone Graph - 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 java를 공부 중이라 연습하는 겸, 이제 알고리즘 문제도 자바로 풀어보려 한다. C++에서도 STL을 자주 사용했더니 java의 컬렉션 프레임워크도 빨리 적응할 수 있는 것 같다. 이번 문제는 인접 노드들을 저장하고 있는 노드들로 그래프를 주면 해당 그래프를 완전히 복사한 새로운 그..

문제 https://leetcode.com/problems/jump-game/ Jump Game - 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 DP풀이 일단 가장 생각하기 쉬운 다이나믹 프로그래밍 풀이부터 소개하겠다. dp[idx]에 idx에서부터 마지막까지 도달할 수 있는 지 여부를 저장한다. dp[end]만 true로 설정하고 뒤에서부터 배열을 순서대로 확인해본다. idx에서는 1~nums[idx]까지 점프할 수 있으므로 dp[..

문제 https://leetcode.com/problems/decode-ways/ Decode Ways - 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 string에서 idx번째인 한자리 수만 알파벳으로 decode한다고 생각해보자. 이를 위해서는 [0~idx-1]까지가 decode가 가능해야한다. 만약 02에서 2를 B로 해석하면 앞의 0는 독립적으로 해석이 되어야 하지만 0은 decode가 불가능하다. 이번에는 idx-1과 idx..