Leetcode 56. Merge Intervals

https://leetcode.com/problems/merge-intervals/

Merge Intervals - LeetCode

 

---

에러코드)

class Solution:
    def merge(self, intervals):
        res = []
        intervals.sort(key= lambda x: x[0])
        if len(intervals) == 1:
            return intervals
        
        for i in range(len(intervals)-1):
            if intervals[i][1] < intervals[i+1][0] or intervals[i+1][0] > intervals[i][1]:
                res.append(intervals[i])
                
            else:
                res.append([min(intervals[i][0],intervals[i+1][0])]+[max(intervals[i+1][1],intervals[i][1])])
                return merge(res)
        return merge(res)

여러 시도를 했지만 이런 에러코드를 짜게됐는데요

처음 접근은 sort를 생각했지만 인덱싱을 통해서 전체 항을 추가 하다보니까 맨 마지막 항이 포함이 안되고 코드가

복잡해졌습니다 ㅜㅠ

 

다른 풀이들을 통해서 어떤 식으로 접근을 해야하는지 살펴봤는데요

 

 

728x90

---

정답 풀이)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        intervals.sort(key=lambda x: x[0])

        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

이 풀이는 Leetcode의 공식 풀이인데요

 

intervals를 sort 하고 

첫번째 if 문에서는 merged 가 비어있거나, 새로 비교하는 값과 이 전의 끝값이 겹치지 않으면 단순 더하고

만약, 겹친다면 항연산을 하는게 아니라 이전의 끝값을 max값으로 교체해주는 방식을 사용했습니다.

 

제 풀이와 가장 큰 차이점은

else의 경우에 전체 리스트를 교체하는게 아니라, 끝값을 교체하는 형식이었는데요

 

---

 

문제를 접근할 때, 이런식으로 리스트 속의 리스트를 처리할 때

리스트를 인덱싱으로 접근하는 법을 주로 사용했는데, 이렇게 항을 별도로 처리하는 방법도 기억하고 넘어가야겠습니다