[Algorithm][LeetCode][Medium][Python] 56. Merge Intervals

문제는 여기서 볼 수 있다.

 

특별한 알고리즘 기법이 필요한 문제는 아니다.

 

---

 

내 풀이

바로 코드 먼저 보자.

 

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 1:
            return intervals
        
        result = []
        intervals.sort(key = lambda x: x[0])
        
        leftIdx, rightIdx = 0, 1
        tempElement = intervals[leftIdx]
        while rightIdx < len(intervals):
            if tempElement[1] < intervals[rightIdx][0]:
                result.append(tempElement)
                leftIdx = rightIdx
                tempElement = intervals[leftIdx]
            else:
                tempElement[1] = max(intervals[leftIdx][1], intervals[rightIdx][1])
            rightIdx += 1
            
        if not result or result[-1][1] != intervals[-1][1]:
            result.append(tempElement)
        
        return result
        

 

우선, 내가 생각한 핵심 알고리즘을 구현하기 전에

 

입력 배열에 대해 sorting이 이루어져야

 

좀 더 쉽게 구현이 가능하다는 생각이 들었다.

 

 

입력 배열은 2차원 배열이므로

 

각 원소 배열의 첫 번째 인자를 기준으로 sorting을 한다.

 

 

그 후, 내가 구현한 핵심 알고리즘은 Two-Pointer 방식이다.

 

 

left 인덱스, right 인덱스를 두고

 

마지막에 return할 result라는 리스트에 붙일

 

tempElement라는 임시 원소 리스트를 만들어간다.

 

 

퍼포먼스는 아래처럼 느린 편이다.

 

 

 

예전 내 풀이

이 문제도 역시나 예전에 풀었던 문제인데,

 

지금 방법보다 훨씬 빠른 퍼포먼스로 풀었더라.

 

 

어이-! 똑똑하잖아 과거의 나 -! ! 

 

 

코드는 아래와 같다.

 

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

 

핵심 알고리즘 부분 빼고 다 똑같다.

 

사실 핵심 알고리즘 부분도 원리는 똑같다.

 

 

단지, Two-Pointer 방식에서 for문으로 바꿨을 뿐이다.

 

 

그런데 퍼포먼스 차이는 아래처럼 차이가 크다.

 

 

---

 

아마 원인은 tempElement 때문인 것 같다.

 

 

최근에 내가 푼 풀이에서는 tempElement라는

 

임시 리스트를 두어 붙여 나가는 방식을 사용했는데,

 

 

예전에 내가 푼 풀이에서는

 

return할 결과 list에 바로바로 붙여나가는 방식을 사용했다.

 

 

러프하게 말하면 append 작업이

 

2번에서 1번으로 줄어들어 퍼포먼스 또한 좋아진 것 같다.

 

 

생각보다 append 작업이 시간을 많이 잡아먹네;

 

 

끝!