[LeetCode] 1642. Furthest Building You Can Reach

문제

https://leetcode.com/problems/furthest-building-you-can-reach/description/

접근

• 힙을 이용한 그리디 알고리즘
  • 반복문을 돌면서 현재 위치한 빌딩과 이전의 빌딩의 차이를 계산하고 양수면 min-heap에 넣는다.
  • 이 때, 힙의 크기가 사다리보다 크면 힙에서 값을 꺼내와 벽돌에서 빼준다. min-heap이므로 현재 구간에서 가장 작은 구간의 값이 나와 벽돌을 쌓은 것으로 볼 수 있고, 가장 큰 값들은 힙 안에 그대로 있을 것이라 사다리를 통해서 해당 구간을 지나 간 것으로 볼 수 있다.

Code

import heapq

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        heap = []
        n = len(heights)
        for i in range(1, n):
            jump = heights[i] - heights[i-1]
            if jump > 0:
                heapq.heappush(heap, jump)
            if len(heap) > ladders:
                bricks -= heapq.heappop(heap)
                if bricks < 0:
                    return i-1
        return n-1