[Python] 프로그래머스 / 2019 카카오 개발자 겨울 인턴십 / 징검다리 건너기

문제 링크

 

정말정말 어려웠던 문제... class Node도 선언해보고 별거 다 해봤지만... 결론은 간단한 이진탐색, 혹은 인덱스가 저장된 heapq를 사용하는 것이었다.

 

윈도우 슬라이싱에 있어서 heapq 사용의 어려움

만약 슬라이싱 윈도우를 list로 관리한다면(최악임) 시간복잡도는 아래와 같다. 여기서 K는 슬라이싱 윈도우의 크기이다.

리스트 사용

즉, O(K)로 최댓값을 찾고, 새로운 윈도우를 O(K)로 구하는 과정을 N번 반복해야 하기 때문에 (N은 전체 리스트 길이)
전체 시간복잡도는 O(NK^2)이다! 이 경우 문제 조건에 의해 최대 8 * 10^15 의 복잡도를 가질 수 있다.

(복잡도는 1억 넘기면 좀 힘들다고 생각하면 편함)

 

→ deque 쓰면 되잖아?

deque 사용

 

이 경우에도 복잡도는 O(NK)이기 때문에 10^10을 넘어가는 복잡도를 보여, 문제 풀이가 불가능하다.

 

→ 그럼 heapq 쓰면 되잖아?

 

이것도... 오히려 deque 쓰는 것보다 더 어려워진다.

 

그냥 간단하게 이진탐색이 답이었다!

def solution(stones, k):
    
    def is_available(number) :
        count = 0 
        for stone in stones :
            if number > stone :
                count += 1
            else :
                count = 0
            if count >= k :
                return False
        
        return True
    
    l, r = 1, max(stones) 
    
    while l <= r :
        mid = (l+r)//2
        
        if is_available(mid) :
            l = mid + 1
        else :
            r = mid - 1
            
    return r

 

이 경우 복잡도는, is_availalbe()이 O(N)이고, 이진탐색이 O(log(max(stones)))이다.

• N <= 2 * 10^5
• stones <= 2 * 10^8

이때 log 시간복잡도를 구하는 꿀팁이 있는데,

• 2 ^ 10 ~ 10 ^ 3
• 2 ^ 20 ~ 10 ^ 6
• 2 ^ 30 ~ 10 ^ 9

이다. 그러므로 2 * 10^8의 log값은 해봤자 30을 넘지 않으리라고 추정 가능하고, 실제로도 27.6쯤 된다. 거기에 O(N)을 곱해봤자 600만 수준이라는 것이 추정 가능하다!

 

인덱스가 저장된 heapq도 사용 가능함 (이게 더 간지남)

슬라이싱 윈도우에서 heapq의 가장 큰 문제점은, 파이썬에서는 min heap밖에 지원이 안 돼서 원소에 -1을 곱해야 해서 좀 까다롭다는 것과, 무엇보다 빼내야 할 원소를 찾기가 매우 어렵다는 것이다. 사실 애초에 deque와 heapq는 그렇게 조화롭지는 못하다고 생각했다. 왜냐하면, 애초에 deque는 heapq.heapify()할 수 없기 때문이다(중요함)!

 

하지만 아래의 코드는 stones는 deque로 처리하고, 슬라이싱 윈도우는 heapq로 처리하여 효율성을 극대화했다. 그리고 heapq에 인덱스를 같이 저장하여, current_idx와 어떤 요소의 인덱스 차이가 일정치를 초과하면 pop하도록 처리했다.

import heapq
from collections import deque

def solution(stones, k):
    
    stones = deque(stones)
    window = []
    
    for idx in range(k-1) :
        heapq.heappush(window, (-stones.popleft(), idx))
        
    answer = -float('inf')
        
    current_idx = k-1
        
    while stones :
        heapq.heappush(window, (-stones.popleft(), current_idx))
        
        while True :
            candidate, candidate_idx = heapq.heappop(window)
        
            if current_idx - candidate_idx < k :
                heapq.heappush(window, (candidate, candidate_idx))        
                break
                
        answer = max(answer, candidate)
        current_idx += 1
        
    return -answer

 

이 코드는 굉장히 효율적이다. O(N logK) 정도 되는데, 최악의 경우에도 400만을 넘지 않는다.