LeetCode 56(Merge Intervals, Python)

1. 문제 링크

• Merge Intervals - LeetCode

Merge Intervals - LeetCode

2. 문제 설명

• 구간을 나타내는 리스트들이 주어졌을 때 겹치는 리스트가 있다면 이를 합쳐서 반환하는 문제
• 예시) intervals = [[1,3],[2,6],[8,10],[15,18]]가 주어지면 [1,3]과 [2,6]은 겹치므로 이를 [1,6]으로 바꾸어 [[1,6],[8,10],[15,18]]를 반환하기

3. 처음 풀이

• [1,3], [2,6], [8, 10], [15, 18]이 있다.
• 우선 [1,3]의 좌우 값을 temp_left, temp_right에 저장한다.
• [1,3] 오른쪽 3과 다음 구간 [2,6]의 왼쪽 2를 비교하면 3이 더 크거나 같으므로 겹치는 것을 알 수 있다.
• 그러면 3과 6중 큰 6으로 temp_right를 업데이트한다.
• temp_right 6과 [8,10] 왼쪽 8을 비교하면 6이 작으므로 겹치지 않는 것을 알 수 있다.
• 그렇다면 temp_left, temp_right로 만들어진 병합 구간 [1, 6]을 result에 추가한다.
• 그 다음 [8,10]의 좌우 값을 temp_left, temp_right에 저장
• [8,10]의 오른쪽 10과 다음 구간 [15,18] 왼쪽 15를 비교하면 10이 더 작으므로 겹치지 않는다.
• 따라서 temp_left, temp_right로 만들어진 병합 구간 [8, 10]을 result에 추가
• 이때 발생하는 edge 케이스는 병합하다가 끝까지 가는 경우, 그리고 마지막 하나만 남은 경우이다. 이 경우는 따로 처리해주었고 edge 케이스를 따로 다루어준 것이 좀 깔끔하지 않은 느낌.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key = lambda x: x[0])

        if len(intervals) < 2:
            return intervals

        result = []
        start, end = 0, 1
        length = len(intervals)

        left = intervals[start][1]
        right = intervals[end][0]

        while end < length:
            temp_left = intervals[start][0]
            temp_right = intervals[start][1]
            while right <= temp_right:
                temp_right = max(temp_right, intervals[end][1])
                if end == length - 1:
                    result.append([temp_left, temp_right])
                    return result
                else:
                    start += 1
                    end += 1
                    left = intervals[start][1]
                    right = intervals[end][0]
            result.append([temp_left, temp_right])
            start += 1
            end += 1
            if start == length - 1:
                result.append([intervals[start][0], intervals[start][1]])
                return result
            else:
                left = intervals[start][1]
                right = intervals[end][0]

        return result

4. 다른 풀이

• 비슷한 논리 구조, 코드가 간결함.
• 일단 오버랩 되지 않는 interval을 결과 merged에 추가해두고 나서 비교하기 때문에 나와 달리 edge case가 생기지 않는다.
• 결과물에 추가해두고 나서 수정을 하는 편이 완성시킨 후 추가하는 것보다 편할 수도 있다.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        merged = []
        for i in range(len(intervals)):
            if merged == []:
                merged.append(intervals[i])
            else:
                previous_end = merged[-1][1]
                current_start = intervals[i][0]
                current_end = intervals[i][1]
                if previous_end >= current_start: # overlap
                    merged[-1][1] = max(previous_end,current_end)
                else:
                    merged.append(intervals[i])
        return merged

---

• unpacking을 이용하면 한층 더 간결하다.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda pair:pair[0])
        output = [intervals[0]]
        for currstart,currend in intervals:
          prevend = output[-1][1]
          if prevend >= currstart:
            output[-1][1] = max(prevend,currend)
          else:
            output.append([currstart,currend])
        return output

5. 배운 점

• 결과물에 추가해두고 나서 수정을 하는 편이 완성시킨 후 추가하는 것보다 편할 수도 있다.
• sort, key, lambda를 이용한 정렬 문법 익혀두기
  • intervals.sort(key=lambda x: x[0])