[LeetCode] 56. Merge Intervals (파이썬)

< 56. Merge Intervals - 파이썬 풀이 >

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 구현코드

문제풀이 아이디어

• 문제에서 요구하는 것은 intervals 내에 범위들 중 겹치는 것은 하나로 뭉쳐서 반환하라는 것이다.
• 해당 문제에서 중요한 것은 intervals 내 범위들이 정렬이 되어있는지가 중요하다. 정렬이 되어있지 않다면 탐색하면서 하나로 뭉치기가 여간 어려운 것이 아니다. 예를 들어, 제일 처음에 [0,0]이란 범위가 나오고 [0,3],[4,5],[0.1] 다음엔 이런 순서의 범위가 있다면 규칙적으로 합치기가 어렵다. 근데 [0,0],[0,1],[0,3],[4,5] 이런 순서로 나열되어있다면? 규칙적으로 합칠 수 있게 된다.
• 그래서 먼저 정렬을 해준다. start 값에 대해서 정렬을 해주고 같다면 end 값에 대해서 정렬을 해주면 좋을 것 같다.
• 그렇게 정렬한다면 경우는 굉장히 한정적으로 변한다. 무조건 start 값은 순차적이고 start가 같다면 end가 순차적이다. 그때의 경우를 생각해자.
• 먼저 내가 선택한 start, end가 뒤에 start, end보다 둘 다 작은 경우이다. 이 경우엔 내가 선택한 start, end를 저장, 삽입하고 start, end를 뒤에 start, end로 바꾼다. -> 이걸 표현하면 내가 선택한 end보다 뒤에 start가 더 큰 경우라고 표현할 수 있다. 즉, 겹치지 않는 부분이다.
  

  

• 두번째는 내가 선택한 end보다 뒤에 start가 더 작은 경우이다. 이 경우엔 두개의 범위를 합쳐야하기 때문에 start는 어짜피 내 값이 더 작거나 같기 때문에 두고 end를 내가 선택한 end와 뒤에 end값 중 더 큰 것을 넣는다. 이렇게 더 큰 값을 넣는 이유는 아래 그림과 같이 겹치는 경우가 2개 이기 때문이다. 즉, 겹치는 부분이다.
  

  

• 이를 이용해서 코드를 짜보자.

구현코드

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result = []
        intervals.sort(key=lambda x:(x[0], x[1])) # 정렬하는 부분

        start = intervals[0][0]
        end = intervals[0][1]
        for i in range(1, len(intervals)+1):
            if i == len(intervals):
                result.append([start, end])
                break
            if end < intervals[i][0]: # 겹치지 않는 부분
                result.append([start, end])
                start = intervals[i][0]
                end = intervals[i][1]
            else: # 겹치는 부분
                end = max(end, intervals[i][1])
        return result