[LeetCode] 1642. Furthest Building You Can Reach

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

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Furthest Building You Can Reach

문제 유형 : 우선순위 큐, 그리디

문제 난이도 : Medium

 

문제

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.

 

당신은 건물들의 높이를 뜻하는 정수 배열 heights, bricks개의 벽돌, ladders개의 사다리가 주어진다.

0번째 건물부터 다음으로 계속 가려고 한다.

만약 다음 건물의 높이가 현재와 같거나 더 낮으면 그냥 갈 수 있고,

더 크면 벽돌 또는 사다리를 이용해야 한다.

벽돌은 높이 차이만큼의 개수를 사용해야 하고, 사다리는 한 개를 사용해야 한다.

 

최적화하여 사다리와 벽돌로 가는 최대 인덱스를 구하시오.

 

 

풀이

벽돌은 많이 소모가 될 수 있고, 사다리는 하나로 어느 높이든 갈 수 있기 때문에, 사다리를 높이 차가 큰 곳에 사용해야 한다.

최대 힙의 우선순위 큐를 이용하면 된다.

 

반복문으로 처음부터 순차적으로 이동한다.

다음 건물과의 높이 차를 구해서, 최대값보다 낮다면 벽돌의 개수를 높이 차만큼 뺀다.

만약 벽돌의 개수가 음수가 된다면(다 소진했다면), 우선순위 큐에서 수를 하나 꺼내서 벽돌의 개수에 추가시킨다.

그리고, 사다리의 개수를 1 감소시킨다. 이러면 기존의 가장 벽돌을 많이 소진한 구간을 사다리로 대체하여 추가 벽돌을 구한다는 의미이다.

만약, 사다리의 개수가 음수가 된다면, 위의 로직을 발동할 수 없어 다음으로 갈 수 없다는 의미로, 순회를 멈춘다.

 

코드

C++

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        const int n = heights.size();
        priority_queue<int> pq;

        int i = 0;
        while(i < n-1) {
            int diff = heights[i+1] - heights[i];

            if(diff <= 0) {
                i++;
                continue;
            }

            bricks -= diff;
            pq.push(diff);
            if(bricks < 0) {
                bricks += pq.top();
                pq.pop();
                ladders--;
            }

            if(ladders < 0) break;
            i++;
        }

        return i;
    }
};

Go

type Item struct {
	value int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].value > pq[j].value
}
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(Item)
	*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func furthestBuilding(heights []int, bricks int, ladders int) int {
	n := len(heights)
	pq := &PriorityQueue{}

	i := 0
	for i = 0; i < n-1; i++ {
		diff := heights[i+1] - heights[i]

		if diff <= 0 {
			continue
		}

		bricks -= diff
		heap.Push(pq, Item{value: diff})
		if bricks < 0 {
			bricks += heap.Pop(pq).(Item).value
			ladders--
		}

		if ladders < 0 {
			break
		}
	}

	return i
}