[디펜스 게임] 코딩테스트 연습 > 연습문제 > 디펜스 게임
※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※
[문제설명]
준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.
- 준호는 처음에 병사 n명을 가지고 있습니다.
- 매 라운드마다 enemy[i]마리의 적이 등장합니다.
- 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
- 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
- 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
- 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
- 무적권은 최대 k번 사용할 수 있습니다.
준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.
준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한사항
- 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 해주세요.
입출력 예
입출력 예 설명
입출력 예#1
- 1, 3, 5 라운드의 공격을 무적권으로 막아내고, 2, 4 라운드에 각각 병사를 2명, 5명 소모하면 5라운드까지 공격을 막을 수 있습니다. 또, 1, 3, 4번째 공격을 무적권으로 막아내고, 2, 5 번째 공격에 각각 병사를 2명, 3명 소모하여 5라운드까지 공격을 막을 수 있습니다. 그보다 많은 라운드를 막는 방법은 없으므로 5를 return 합니다.
입출력 예#2
- 준호는 모든 공격에 무적권을 사용하여 4라운드까지 막을 수 있습니다.
[간단설명]
주어진 병사수(N)로 무적권(K)을 사용했을때, 가장 많이 막을 수 있는 라운드 리턴
[접근방법]
1. 우선순위 큐를 만들어서, 내림차순 정렬한다.
2. 현재병사수(N) 보다 적의수가 작은 경우
2.1. 현재병사수(N) 에서 적의수를 차감하면서, 큐에 적의수를 저장하고, 라운드를 증가시킨다.
3. 현재병사수(N) 보다 적의수가 큰 경우
3.1. 무적권이 있으면,
3.1.1. 큐에서 꺼낸값이 적의수보다 크면, N을 복원하고, 적의수를 차감하고, 큐에 적의수를 저장한다.
3.1.2. 큐가 비었거나, 큐에서 꺼낸값이 적의수보다 작으면 3.1.3 처리만한다.
3.1.3. (3.1.1, 3.1.2) 모두 무적권을 사용처리하고, 라운드를 증가시킨다.
3.2. 무적권이 없으면, 종료 처리
4. 진행라운드 리턴
[주의사항]
- 우선순위큐의 사용법을 숙지하자.
- 무적권 사용시, 병사를 복원하고, 현재 적의수를 차감하는 과정이 필요하다.
[소스공개]
import java.util.*;
class Solution {
public int solution(int n, int k, int[] enemy) {
// 우선순위큐
PriorityQueue<Integer> pQue = new PriorityQueue<>(Collections.reverseOrder());
// 진행라운드
int round = 0;
// 적의 공격 순회
for(int i=0;i<enemy.length;i++){
// 현재병사로 적을 막을수 있으면
// n에서 현재 적의수 차감
// pQue에 현재 적의수 저장
// 라운드 증가
if(n>=enemy[i]){
n-=enemy[i];
pQue.offer(enemy[i]);
round++;
// 현재병사로 적을 막을수 없으면
}else{
// 무적권이 남아 있으면
if(k>0){
// pQue에 숫자가 있는 경우,가장 큰 숫자를 꺼내서, 무적권 사용처리
// 라운드 증가
// n은 병사복원
// n에서 현재 적의수 차감
// pQue에 현재 적의수 저장
if(!pQue.isEmpty()){
if(pQue.peek()>enemy[i]){
n+=pQue.poll();
n-=enemy[i];
pQue.offer(enemy[i]);
}
}
// pQue에 숫자가 없는 경우는, 현재 적의수를 무적권 사용처리
// 라운드 증가
round++;
k--;
// 무적권이 없으면, 라운드 종료
}else{
break;
}
}
}
// 진행라운드 리턴
return round;
}
}
[실행결과]
