문제 정의
높이가 서로 다른 n개의 건물이 있고, 한 명의 파쿠르 예술가가 벽돌과 사다리를 이용해 건물 사이를 이동하려고 합니다. 각 건물의 높이는 배열로 주어지며, 벽돌 하나의 길이는 1입니다. 사다리와 벽돌은 각각 한 번씩만 사용할 수 있으며, 이 예술가가 도달할 수 있는 가장 먼 건물의 위치를 구해야 합니다.
예를 들어 heights = [5, 8, 7, 6, 2, 3, 1, 4], bricks = 3, ladders = 2가 입력으로 주어지면 출력은 7이 됩니다.
이동 과정 살펴보기
- 예술가는 0번 건물에서 출발합니다.
- 벽돌 3개를 모두 사용해 1번 건물로 올라갑니다.
- 2번, 3번, 4번 건물은 앞선 건물보다 낮기 때문에 점프만으로 자유롭게 이동합니다.
- 사다리 하나를 사용해 4번 건물에서 5번 건물로 이동합니다.
- 6번 건물이 5번보다 낮으므로 점프해 넘어갑니다.
- 마지막으로 남은 사다리를 사용해 7번 건물에 도달합니다.
알고리즘 접근 방법
이 문제는 그리디(greedy) 전략과 최소 힙(min-heap)을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 오르막 구간에서는 우선 벽돌을 사용합니다.
- 벽돌이 부족해지는 순간, 지금까지 벽돌로 오른 가장 큰 상승 폭을 사다리로 대체합니다.
- 사다리까지 모두 소진되었는데도 벽돌이 부족하다면, 그 직전 건물이 최종 도달 지점입니다.
구체적인 풀이 단계는 다음과 같습니다.
- temp라는 이름의 새로운 힙을 생성합니다.
- i를 1부터 heights의 길이까지 반복합니다.
- dist := heights[i] - heights[i - 1]로 인접한 두 건물의 높이 차를 계산합니다.
- dist > 0인 경우(오르막):
- bricks에서 dist만큼 차감합니다.
- -dist 값을 힙 temp에 push합니다.
- bricks < 0이 되면:
- ladders를 1 감소시킵니다.
- 힙에서 가장 작은 원소, 즉 지금까지 가장 컸던 상승 폭의 음숫값을 꺼내(bricks -= heappop(temp)) bricks에 다시 더합니다. 이는 해당 구간을 벽돌 대신 사다리로 통과했음을 의미합니다.
- 그래도 bricks < 0 또는 ladders < 0이라면 i - 1을 반환합니다.
- 반복문이 끝날 때까지 중단되지 않았다면 마지막 건물(len(heights) - 1)까지 이동할 수 있으므로 이를 반환합니다.
파이썬 구현 예제
아래 구현을 통해 동작 방식을 더 잘 이해해 보겠습니다.
from heapq import heappush, heappop
def solve(heights, bricks, ladders):
temp = []
for i in range(1, len(heights)):
dist = heights[i] - heights[i - 1]
if dist > 0:
bricks -= dist
heappush(temp, -dist)
if bricks < 0:
ladders -= 1
bricks -= heappop(temp)
if bricks < 0 or ladders < 0:
return i - 1
return len(heights) - 1
print(solve([5, 8, 7, 6, 2, 3, 1, 4], 3, 2))입력
[5, 8, 7, 6, 2, 3, 1, 4], 3, 2
출력
7
동작 원리 요약
힙에는 매번 -dist(상승 폭의 음수)가 저장되므로, 힙에서 원소를 꺼내면 항상 지금까지 가장 큰 상승 폭이 나옵니다. 벽돌이 바닥나는 순간 그 가장 큰 상승 폭을 사다리로 되돌려주면, 남은 벽돌로 나머지 오르막을 처리할 수 있는지 다시 판단할 수 있습니다. 이 방식 덕분에 벽돌과 사다리를 항상 최적으로 배분할 수 있으며, 전체 시간 복잡도는 O(n log n)입니다.