파이썬 - merge intervals

목차

시작
문제 1: 기본적인 문제

문제 2: merge intervals

1시간 30분 동안 헛짓하다 틀린 문제
정리

시작

merge interval 유형은 구글 코딩 인터뷰에서 자주 등장하는 유형인 만큼 중요합니다.

merge interval이름은 '구간을 합치다'라는 뜻을 가지고 있습니다.

이 알고리즘의 경우 이론에 복잡한 내용이 없습니다.

직관적으로 예제를 통해 익히면 쉽게 접근할 수 있으니,

바로 문제를 풀어 봅시다.

1. 가장 기본적인 merge intervals

https://leetcode.com/problems/teemo-attacking/

Teemo Attacking - LeetCode

문제는 대략 이렇습니다.

티모와 에쉬가 있습니다.

티모가 에쉬를 공격하면 에쉬는 독에 감염됩니다.

독이 감염되는 시간은 인풋 데이터 duration으로 주어집니다.

 

티모가 애쉬를 언제 공격했는지 시간을 담은 리스트 timeSeries가 인풋으로 주어질 때,

애쉬가 독에 시달린 총시간을 구하는 문제입니다.

 

구속 조건(꼭 보삼)

• 1 <= timeSeries 길이 <= 10**4
• 0 <= timeSeries [i], duration <= 10**7
• timeSeries는 시간순으로 정렬되어 있음

현실에 충실하게 무지성으로 구현하기

초기 시간 0초부터 시작해서 시간을 늘리며 진행합니다.

그리고 문제에 주어진 조건을 똑같이 구현하면 끝!

 

요런 식으로 구현하면 

시간을 순차적으로 늘리는데 O(10**7 )의 시간복잡도를 사용합니다.

이는 O(10,000,000)으로 문제에서 O(n)의 시간 복잡도를 원한다면 간당간당하게 통과되거나 시간 초과 판정을 받습니다. 아래의 코드는 간당간당하게 시간 초과 판정을 받아 실패한 코드입니다.

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        count = 0
        t = 0
        tset = set(timeSeries)
        answer = 0
        while True:
            if tset == set() and count == 0: break
            if count > 0: 
                answer += 1
                count -= 1
            if t in tset: 
                tset.remove(t)
                count = duration
            t += 1
        return answer

그럼 어떻게 구현해야 하는데? merge intervals

이 문제는 timeSeries에 대한 for loop 한 번으로 해결 가능합니다.

어떻게 하면 가능할까요?

이를 위해 간단한 예제를 분석해 봅시다.

총 3번의 티모 공격이 있었습니다.

1번의 경우 모두 독이 완전이 끝난후 다시 공격한 경우입니다.

2번의 겅우 모두 독이 끝나지 않았을 때 다시 공격한 경우입니다.

 

이 예를 보면 2가지의 경우로 생각해 볼 수 있습니다.

• 독이 끝나기 전 다시 티모가 공격하여 중첩된 경우
• 중첩되지 않은 경우 

for loop를 돌며 중첩된 경우 시간을 카운트하기 위해서는 아래와 같이 더해야 합니다.

시간 =  timeSeries[2] - timeSeries[1]
     + timeSeries[3] - timeSeries[2]
     + duration

중첩되지 않은 경우는

시간 =  duration
     + duration
     + duration

요런 식으로 더해야 합니다.

 

결국 중첩된 경우면 시간에 t += timeSeries [i+1] - timeSeries[i]를 진행하면 되고,

중첩되지 않았다면  t += duration을 진행하면 됩니다.

 

또한 중첩이 된 경우 timeSeries [i+1] - timeSeries [i]의 값은 duration보다 작습니다.

이 성질을 이용하면 코드를 깔끔하게 작성할 수 있습니다.

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        n =  len(timeSeries)
        if n == 0: return 0
        t = 0
        for i in range(n-1):
            t += min(timeSeries[i+1]-timeSeries[i], duration)
        return t + duration

 

직접적인 merge intervals

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

Merge Intervals - LeetCode

문제는 대략 이렇습니다.

구간을 가지는 리스트가 주어집니다.

리스트의 성분인 구간은 아래와 같이 정의되어 있습니다.

• 리스트의 각 성분은 [시작, 끝]으로 구성되 있습니다.

구속조건(꼭 고려):

• 1 <= intervals 길이 <= 10**4
• intervals[i] 길이 == 2
• 0 <= 시작 <= 끝 <= 10**4

이전 문제에서 얻은 지식으로 바로 적용해 보기

이 문제는 merge intervals유형입니다.

인풋으로 들어오는 intervals의 길이를 n이라할 때 O(nlogn)으로 해결가능합니다.

 

그럼 의사코드를 작성해 봅시다.

1. intervals의 성분에서 시작을 기준으로 정렬합시다.

2. 리턴할 데이터를 담을 result = [] 만듭시다.
   또한 병합시 임시로 저장할 dum = [intervals[0]]를 만듭니다.

3. intervals를 for loop를 돌며 result에 병합하고 값을 추가합시다. 
    
    4. 만약 dum[1]이 interval[1]보다 크면, dum과 interval을 합칩니다.
    
    dum[0]는 가장 작은 값이 기에 가만히 두고 dum[1]은  max(dum[1], interval[1])로 처리합니다.
    
    5. 4번의 경우가 아니면 dum을 result에 추가합니다.
       그리고 dum = interval로 설정하여 다음을 준비합니다.
       
 6. 마지막의 dum이 추가 되지 않았기 때문에 result.append(dum)을 진행하여 정답을 제출합니다.

위의 의사코드로 진행하게 되면 O(nlogn)으로 해결 가능합니다.

정렬에 O(nlogn)사용이 되고 loop에서 O(n)이 사용되기 떄문입니다.

구현

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key = lambda x : x[0])
        dum = intervals[0]
        result = []
        for interval in intervals:
            if dum[1] >= interval[0]:
                dum[1] = max(interval[1], dum[1])
            else:
                result.append(dum)
                dum = interval
    
        result.append(dum)
        return result

 

 

https://programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

https://programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러

https://programmers.co.kr/learn/courses/30/lessons/72414

코딩테스트 연습 - 광고 삽입