[파이썬 알고리즘 인터뷰][정렬] 구간 병합

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

[start, end] 구간의 리스트가 주어질 때, 이 구간들의 겹치는 부분을 병합하여 출력

 

책에서 구현된 코드

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        merged = []
        for i in sorted(intervals, key=lambda x: x[0]):
            if merged and i[0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], i[1])
            else:
                merged += i,
        return merged

 

기억해야할 기법

• 겹치는 구간 병합 문제에서 내가 빠지는 함정
  
  • 항상 이런 문제에서 효율적인 방법을 고안하다가 시간이 오래걸림
  • 반복문을 통한 비교
    - 겹치면 결과 리스트에 append하지 않으려고함
    - start 인덱스를 유지하고 continue하려함
    - continue는 마지막 구간을 추가하지 못해 문제
  • start와 end를 서로 다른 큐로 처리
    - 정렬이 된 상태에서 구간을 start와 end로 분리하여 순서대로 처리
    - 나름 깔끔하고, 마지막 구간까지 추가할 수 있음
    - 그러나 두 구간의 관계가 포함관계일 때 처리가 불가능(start와 end가 각각 정렬되어야함)
  • start와 end를 서로 다른 우선순위 큐로 처리
    - 되긴 된다
    - 그러나 시간 복잡도에서 더 비효율적이다
    - sorting 후 반복비교 : O(n log n) + O(n)
    - start/end 분리된 힙을 만들어서 pop : O(2n log 2n) + O(2n log 2n)
• 결론적으로 반복문에서 append를 보류하는게 더 효율적이라는 착각부터 문제
  • 반복문의 문제는 마지막 append될 요소가 문제였음
  • append를 미리 하는 것이 하지 않아도 될 불필요한 작업이라 생각함
  • 그러나 추가될 요소를 미리 추가하고, 그 값을 바꾸는 과정임

 

내가 구현한 코드

# Fail : 책보고 구현
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result = []
        for start, end in sorted(intervals, key=lambda x: x[0]):
            if result and end <= result[-1][1]:
                continue
            if result and start <= result[-1][1]:
                result[-1][1] = end
            else:
                result.append([start, end])

        return result

# 우선순위 큐
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result = []
        start = []
        end = []
        for _start, _end in intervals:
            heapq.heappush(start,_start)
            heapq.heappush(end,_end)

        while start and end:
            s = heapq.heappop(start)
            while start and end and start[0] <= end[0]:
                heapq.heappop(start)
                heapq.heappop(end)
            e = heapq.heappop(end)
            result.append([s,e])
        return result

• 정렬에 관련된 문제는 잘 안다고 생각했는데, 정렬된 데이터를 활용하는 로직이 미흡한 것 같다
• 항상 느끼지만, 불필요하다고 생각하는 부분이 있으면 그 부분을 어떻게든 빼려고 구현조차 못하는 것 같다
  - 이 문제에서는 요소에 append를 먼저 하는 것이었다
  - 이 방법이 비효율적이라고 착각한 것도 문제지만, 우선 구현하고 고민했다면 착각이었다는 걸 깨달았을 것이다