[Java] LeetCode 56: Merge Intervals

[문제 바로 가기] - Merge Intervals

리트코드에서 처음 풀어보는 문제!
이번 가비아 코딩테스트 1번과 비슷한 문제라서 스터디에서 다같이 풀어보기로 했다.

💡 접근 방식

처음에는 가비아 코딩테스트에서 풀었던대로 풀어보려 했지만 로직의 한계인지 답이 나오지 않아 풀이를 참고했다.

먼저 Arrays.sort를 사용해서 intervals 배열을 정렬해주는데 첫번째 값을 기준으로 정렬해줘야 한다.
이때 값 비교할 때는 Integer.compare 함수 사용하기!

Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));

(1) 구간을 저장할 merged가 비었거나, merged의 마지막 값[1]이 interval[0]보다 작을 땐 겹치지 않는다는 뜻이므로merged.add(interval);
(2) 둘 다 해당하지 않을 경우(=범위가 겹칠 경우) merged의 마지막 값[1]을 interval[1]과 비교해서 큰 값으로 갱신한다. = 구간 합치기

★ List를 배열로 바꾸는 방법

• java.util.List의 toArray() 함수 사용
• 배열의 크기를 선언할 때 행의 크기는 0, merged.size() 중 아무거나 해도 된다.
  • 전달 받은 list의 크기가 지정한 크기보다 크다면 그만큼 자동으로 늘어난다.
  • 지정한 크기보다 작아 남는 배열이 있다면 null로 채워진다.
• 열의 크기를 설정해주지 않아도 되는 이유는 각 int[]의 길이는 이미 정해져 있기 때문에, 추가로 크기를 지정할 필요가 없다.

// 둘 다 가능

merged.toArray(new int[merged.size()][]);
merged.toArray(new int[0][]);

---

풀이

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));

        List<int[]> merged = new ArrayList<>();

        for (int[] interval : intervals) {
            int size = merged.size();
            if (merged.isEmpty() || merged.get(size - 1)[1] < interval[0]) merged.add(interval);
            else merged.get(size - 1)[1] = Math.max(merged.get(size - 1)[1], interval[1]);
        }

        return merged.toArray(new int[merged.size()][]);
    }
}