Leetcode 1642. Furthest Building You Can Reach

문제

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

If the current building's height is greater than or equal to the next building's height, 
you do not need a ladder or bricks.

If the current building's height is less than the next building's height, 
you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach 
if you use the given ladders and bricks optimally.

당신에게 횡방향의 건물들과 몇개의 벽돌과 몇개의 사다리가 주어진다.
당신이 건물 사이를 이동할때 이전의 건물이 다음 건물보다 낮거나 같으면 그냥 이동 가능하지만
만약 다음 건물이 더 높다면, 반드시 그 높이만큼의 벽돌이나 사다리 한개를 소모해야 한다.
당신이 최고로 멀리 갈수 있는 건물의 index는 어디인가?

예시

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: 
4 -> 2 : 아래에 있어 바로 이동 가능
2 -> 7 : 주어진 5개의 벽돌을 모두 사용한다.
7 -> 6 : 아래에 있어 바로 이동 가능
6 -> 9 : 벽돌이 남은게 없어 사다리 한개 사용
9 -> 14: 사다리 벽돌이 남은게 없어 이동 불가능
- 최대로 이동할수 있는 건물의 index는 높이 9짜리 건물인 4이다.

제한

• 1 <= heights.length <= 10^5
• 1 <= heights[i] <= 10^6
• 0 <= bricks <= 10^9
• 0 <= ladders <= heights.length

풀이법

이 풀이법은 MaxHeap을 사용한다.
순서는 아래와 같다.
0. Maxheap m을 만든다.
1. 다음 건물이 낮으면 그냥 이동한다.
2. 다음 건물이 높으면 일단 벽돌을 써서 이동하고 남은 벽돌에서 그 높이만큼을 뺀다.
2.1 - 벽돌을 사용한 갯수는 m에 push 한다.
3. 만약 벽돌의 갯수가 양수나 0이면 벽돌로 올라갈수 있기에 넘어가나 음수가 된다면 아래 절차를 진행한다.
4. 만약 남은 사다리가 없으면 현재 위치를 리턴한다.
5. 사다리가 있으면 m에서 가장 큰 값을 가져오는데, 이는 벽돌을 사용한 가장 많은 횟수이다. 이걸 벽돌의 갯수에 더하고
그 위치에 사다리를 사용해 사다리를 하나 제한다.

from heapq import heappop, heappush

class MaxHeap:
    def __init__(self):
        self.arr = []
    
    def push(self, val):
        heappush(self.arr, -val)

    def peek(self):
        if len(self.arr) == 0:
            return None
        return -self.arr[0]

    def pop(self):
        if len(self.arr) == 0:
            return None
        return -heappop(self.arr)

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        m = MaxHeap()

        for i in range(len(heights) - 1):
            diff = heights[i + 1] - heights[i]
            if diff <= 0:
                continue
            
            bricks -= diff
            m.push(diff)

            if bricks < 0:
                if ladders == 0:
                    return i
                ladders -= 1
                bricks += m.pop()

        return len(heights) - 1
        

• 사실상 MaxHeap 구현이 길이가 맞먹는다 ㅋㅋ