문제 요약
n명의 병사로 연속되는 적의 공격을 순서대로 막는 디펜스 게임이다.
시작할 때,n의 병사가 주어지며 매 라운드마다 등장하는enemy[i]마리를 상대하면n명의 병사 중enemy[i]마리를 소모해야 한다.
다행이 한 라운드를 넘길 수 있는k개의 무적권이 주어질 때, 무적권을 적절히 사용하여 최대 몇 라운드까지 살아남을 수 있는지 계산해보자
[ 예시 ]
| n | k | enemy | result |
|---|---|---|---|
| 7 | 3 | [4, 2, 4, 5, 3, 3, 1] | 5 |
| 2 | 4 | [3, 3, 3, 3] | 4 |
[ 제약 조건 ]
- 1 ≤ n ≤ 1,000,000,000
- 1 ≤ k ≤ 500,000
- 1 ≤ enemy의 길이 ≤ 1,000,000
- 1 ≤ enemy[i] ≤ 1,000,000
- enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.
[ 프로그래머스 ]
풀이
- 일단 계산하고, 과거 이력 중
enemy[i]의 수가 가장 큰 경우에 무적권을 사용하여n의 값을 최대로 유지해야 한다. - 최대 값을 갖는 과거 이력을 확인하기 위해
PriorityQueue를 사용한다.
(1) 라운드별로 n 병사들로 적을 상대하고 남은 병사를 n에 저장한다.
(2) 그 결과 n이 음수일 경우 더 이상 라운드를 진행할 수 없기에 무적권이 필요하게 된다.
(3) 무적권이 있는 경우엔 무적권을 사용하여 과거 그 라운드는 건너뛰게 만든다.
- 최대 힙으로 선언한
PriorityQueue의 가장 앞 요소를 꺼내n에 더하고, 무적권(k)의 수는 1개 줄인다. - 그럼에도 여전히 음수이면, 다시 한 번 과거 이력을 무적권으로 넘긴다.
(4) 무적권을 모두 소비했다면, 더 이상 라운드를 진행할 수 없음으로 i값을 최대 라운드로 지정한다.
Code
import java.util.*;
class Solution {
public int solution(int n, int k, int[] enemy) {
int answer = enemy.length;
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
for(int i=0;i<enemy.length;i++) {
n -= enemy[i];
queue.add(enemy[i]);
// 음수임으로, 무적권 사용 필요
if (n < 0) {
// 무적권이 있는 경우
if (k > 0 && !queue.isEmpty()) {
n += queue.poll();
k--;
// 무적권을 모두 소비한 경우
} else {
answer = i;
break;
}
}
}
return answer;
}
}시도
문제를 보자마자, 완전탐색과 그리드가 생각났다. 하지만 완전탐색을 하자니 각 값의 최대 값이 크기 때문에 시간초과가 걸렸을 거 같다.그리드를 해보기에 앞서 아래 방식들을 시도해봤다.
1) 평균값을 이용
enemy 원소들의 평균값을 구하여, 각 원소별 평균값 이하면 라운드를 진행(n값 감소)하고 값을 초과하면 무적권을 사용하는 식은 어떨까는 생각에 일단 시도해본 방식이다.
주어진 2개의 예시는 통과하였으나, 채점 결과 37.5로 실패하였다.
느낀점
문제가 길어지면 한 번에 이해하기 힘들어 여러 번 읽게 되고, 그게 또 시간을 잡아먹는 듯 하다. 이번 문제는 그나마 짧은 편이라 금방 이해했지만 저번 문제의 경우 이해하는데 다른 문제에 비해 좀 걸렸다. 문제를 읽을 때마다 국어 지문 읽는 기분이라 책을 많이 읽어야겠다는 생각이 들었다. ㅠ
