[Programmers] 징검다리 건너기 (Python)

📖  문제

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

코딩테스트 연습 - 징검다리 건너기

 

💻  코드

from collections import defaultdict
import heapq


def solution(stones, k):
    hq = [-stones[i] for i in range(0, k)]
    heapq.heapify(hq)
    dt = defaultdict(int)
    for i in range(0, k):
        dt[stones[i]] += 1
    answers = [-hq[0]]
    # 투 포인터(Two Pointers) 선언
    start, end = 1, k
    while end < len(stones):
        # 삭제
        dt[stones[start - 1]] -= 1
        # 삽입
        dt[stones[end]] += 1
        heapq.heappush(hq, -stones[end])
        # 조회 후 비교 (Greedy)
        while dt[-hq[0]] == 0:
            heapq.heappop(hq)
        answers.append(-hq[0])
        start, end = start + 1, end + 1
    return min(answers)

🙌  한마디

투 포인터와 그리디 알고리즘을 사용하여 풀었다. 범위 k의 투 포인터를 지정한다. 그런 후 start와 end를 1씩 증가시키며 구한 부분 최적해(두 포인터 범위 내의 최댓값)들의 집합이 전체 문제의 해답(그 중 최솟값)이 되는 그리디(Greedy) 형태로 문제를 풀 수 있다.

 

시간 복잡도를 줄이기 위해 max heap과 딕셔너리를 동시에 이용했다. heap은 최솟값(또는 최댓값) 조회는 O(1), 원소 추가는 O(logN)이 걸리므로 효율적이지만,  특정 원소를 삭제하는데는 어려움이 있다. 따라서 딕셔너리를 추가하여 삽입/삭제 정보를 저장하고 힙과 연동하여 이러한 구조적 문제를 한정적으로 해결하였다. (완전한 해결방법이라고 보긴 어렵고, 해당 문제에 대해서는 잘 작동한다.)

 

추가적으로, 이진 탐색 방법을 통해서도 구현할 수 있다고 한다.