준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n
명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.
n
명을 가지고 있습니다.enemy[i]
마리의 적이 등장합니다.enemy[i]
명 만큼 소모하여 enemy[i]
마리의 적을 막을 수 있습니다.
무적권
이라는 스킬이 있으며, 무적권
을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.무적권
은 최대 k
번 사용할 수 있습니다.준호는 무적권
을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.
준호가 처음 가지고 있는 병사의 수 n
, 사용 가능한 무적권의 횟수 k
, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy
가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.
n
≤ 1,000,000,000k
≤ 500,000enemy
의 길이 ≤ 1,000,000enemy[i]
≤ 1,000,000enemy[i]
에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.enemy[i]
의 길이를 return 해주세요.n | k | enemy | result |
---|---|---|---|
7 | 3 | [4, 2, 4, 5, 3, 3, 1] | 5 |
2 | 4 | [3, 3, 3, 3] | 4 |
입출력 예#1
입출력 예#2
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
이 문제에 핵심은 우선 순위 큐를 사용해야 한다.
- 우선 우선 순위 큐를 사용하기 위해 관련 클래스를 정의한다.
- 큐를 만들어두고 capacity 변수를 정의한다. -> 이 변수는 무적권을 쓰지 않고 얼마나 처리했는지에 대한 합이다.
- 처음 0~k까지 잘라서 그 값을 우선 순위 큐에 넣어둔다.
-> k까지는 무적권을 쓰면 고려대상에서 제외- k부터 enemy끝까지 배열을 아래과정을 돈다.
1) enemy값을 우선 순위 큐에 넣고 제일 큰 값을 pop한다.
2) pop한 값과 capacity를 더해서 n을 넘으면 여기서 stop
-> enemy몇번째까지 했는지 리턴
3) 안넘는다면 그 값은 capacity에 더해준다. -> 무적권을 쓰지 않고 처리한 값- 만약 한 바퀴 돌았는데 리턴되지 않았으면 모든 enemy를 돌고도 n을 넘지 않은 것이기 때문에 enemy 개수 전체 리턴
class PriorityQueue {
constructor() {
this.heap = [];
}
push(value) {
const heap = this.heap;
heap.push(value);
let index = heap.length - 1;
let parent = Math.floor((index - 1) / 2);
while (index > 0 && heap[index] < heap[parent]) {
[heap[index], heap[parent]] = [heap[parent], heap[index]];
index = parent;
parent = Math.floor((index - 1) / 2);
}
}
pop() {
const heap = this.heap;
if (heap.length <= 1) {
return heap.pop();
}
const output = heap[0];
heap[0] = heap.pop();
let index = 0;
while (index * 2 + 1 < heap.length) {
let left = index * 2 + 1, right = index * 2 + 2, next = index;
if (heap[next] > heap[left]) {
next = left;
}
if (right < heap.length && heap[next] > heap[right]) {
next = right;
}
if (next === index) {
break;
}
[heap[index], heap[next]] = [heap[next], heap[index]];
index = next;
}
return output;
}
}
function solution(n, k, enemy) {
let arr = new PriorityQueue();
var capacity = 0;
//k번째까지는 일단 무적권 쓰면 capacity의 고려 대상에서 제외
enemy.slice(0,k).forEach((element)=>arr.push(element));
for(var i =k;i<enemy.length;i++){
arr.push(enemy[i]);
var popNum = arr.pop();
if(popNum+capacity>n){
return i;
}
capacity+=popNum;
}
return enemy.length;
}
이 문제에 핵심은 우선 순위 큐를 사용하는 것이었다. 우선 순위 큐를 사용하지 않고 정렬을 계속해서 하면 답은 나올 수 있겠지만 시간복잡도가 매우 높게 잡힌다. 따라서 이를 해결하기 위해서는 우선 순위 큐가 필수가 되는 문제였다.