2019 카카오 개발자 겨울 인턴십 풀이

Level 1 - 크레인 인형뽑기 게임 풀이
Level 2 - 튜플 풀이
Level 3 - 불량 사용자 풀이
Level 4 - 호텔 방 배정 풀이
Level 3 - 징검다리 건너기 풀이

프로그래머스 - 징검다리 건너기 링크
(2022.11.01 기준 Level 3)

문제

밟을 수 있는 횟수가 적힌 디딤돌로 이루어져 있는 징검다리를 건넌다고 했을 때, 밟을 수 있는 가장 가까운 디딤돌을 무조건 밟아야 하며 k칸 넘게 뛰어 넘지 못한다.
이 때, 징검다리를 건널 수 있는 최대 사람 수 반환

알고리즘

k 크기의 윈도우를 미끄러뜨리면서 각 구간마다의 최댓값을 구하는 heap을 구현해야 한다.

풀이

예제처럼 k가 3일 때를 가정해서 한 그림을 그려보았다.

맨 왼쪽이 현재 있는 디딤돌이라면 파란색 화살표는 가능한 방향, 빨간색 화살표는 불가능한 방향이다. 이 문제는 밟을 수 있는 디딤돌 중 가장 가까운 디딤돌을 무조건 밟아야 한다.

그렇다면 위 그림처럼 밟을 수 있는 횟수가 주어졌다면?
1명 - [4, 2, 1, 0, 3]
2명 - [3. 1, 0, 0, 2]
3명 - [2, 0, 0, 0, 1]
더 이상은 불가능하다. 뭔가 보이지 않는가?
가운데 구간의 최댓값만큼 가능했다. 정확하게는 k 크기의 구간의 최댓값.
그럼 다시 문제 예제를 살펴보면

각 구간의 최댓값을 구하여 모든 최댓값들의 최솟값이 정답이 되는 것을 확인할 수 있다.

그래서 k 크기의 윈도우를 미끄러뜨리면서 각 구간의 최댓값을 구해야 하는 것이다.
그런데 각 구간의 합도 아니고.. 최댓값은 어떻게 구해야 할까?
아마 구간마다 max 연산을 하면 시간 초과가 날 것이다.
그래서 내가 생각한 것은 최대 힙.

먼저 힙에 k 구간만큼 (-횟수, 인덱스)를 넣자. 그리고 현재 인덱스가 i라면 최대 힙의 맨 앞 원소의 인덱스가 i - k + 1보다 같거나 커야하는 것이다. 작다면 같거나 클 때까지 pop 하자. 그러면 각 구간의 최댓값이 구해지는 것이다.

코드

import heapq
from math import inf

def solution(stones, k):
    n = len(stones)

    # 최대 힙 방식으로 각 구간의 최댓값을 구할 것이다.
    queue = []
    answer = inf

    # 먼저 0부터 k - 2 까지 최대 힙에 인덱스와 함께 넣자.
    for i in range(k - 1):
        heapq.heappush(queue, [-stones[i], i])

    # k - 1부턴 하나씩 최대 힙에 넣자.
    # 최대 힙의 맨 앞의 인덱스가 i - k + 1보다 작다면 구간을 벗어난 원소
    # 구간을 벗어난 원소를 전부 pop
    for i in range(k - 1, n):
        heapq.heappush(queue, [-stones[i], i])
        while queue[0][1] < i - k + 1:
            heapq.heappop(queue)
        answer = min(answer, -queue[0][0]) # 답은 각 구간의 최댓값들의 최솟값

    return answer

여담

개인적으론 호텔 방 배정보다 어려웠다고 생각한다. 그래도 2019 카카오 개발자 겨울 인턴십 문제들은 대체적으로 쉬운 것 같다.