59. Merge Intervals

🎯 leetcode - 56. Merge Intervals

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 59번 문제

📌 날짜

2020.02.26

📌 시도 횟수

5 try

💡 Code

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result = []
        for i in sorted(intervals):
            if result and i[0] <= result[-1][1]:
                new_left = result[-1][0]
                new_right = max(result[-1][1], i[1])
                result.pop()
                result.append([new_left, new_right])
            else:
                result.append([i[0], i[1]])

        return result

💡 문제 해결 방법

• 아래 풀이 그림을 보면 이해가 된다.
  

✔ 풀이 과정
1. *정렬된 intervals list*에 대하여 아래 과정을 진행한다.
2. 처음 값은 바로 result 리스트에 넣는다.
3. 두번째 값부터 비교를 진행한다.
- 만약 바로 이전 값의 2번째 자리 값보다 현재 값의 첫번째 자리 값이 더 작은 경우 병합을 진행한다.
> 예를 들어...
이전 값 : (1, 3)
현재 값 : (2, 6)
인 경우 3보다 2가 작으므로 
new_left = 1 (이전 값의 첫번째 값)
new_right = 6 (max(3, 6))
를 설정하여 이전 값을 제거하고 새롭게 병합하여 갱신한 (new_left, new_right)를 넣는다.

💡 새롭게 알게 된 점

- 처음에는... 이렇게 코드를 짰었다.
>> new_left = min(result[-1][0], i[0]) 
- 그러나 값을 순회하기 이전에 처음부터 정렬된 sorted(intervals)를 사용하므로
항상 new_left = result[-1][0]임을 깨달았다. 따라서 이렇게 고쳐주었다.
>> new_left = result[-1][0]

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---