알고리즘/프로그래머스
디펜스 게임
코딍코딍
2023. 6. 14. 18:45
https://school.programmers.co.kr/learn/courses/30/lessons/142085
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
소스코드
import java.util.PriorityQueue;
import java.util.Collections;
class Solution {
public int solution(int n, int k, int[] enemy) {
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < enemy.length; i++) {
if (enemy[i] <= n) {
answer += 1;
n -= enemy[i];
pq.add(enemy[i]);
} else {
if(k <= 0) break; //무적권이 없는 경우
answer += 1;
n -= enemy[i];
pq.add(enemy[i]);
n += pq.poll();
k -= 1;
}
}
return answer;
}
}
해결방법
무적권을 적절한 시기에만 쓰면 되는 문제이다. 가진 병사의 수로 적을 디펜스 하다 병사의 수가 부족하면 무적권을 쓰면 된다. 이때 지금까지 디펜스 한 적들 중 가장 인원이 많았던 그룹에 무적권을 사용해야 한다. 그래야 적절한 시기에 사용하게 되고 최대한 많은 라운드를 갈 수 있다.
가장 인원이 많았던 그룹에 무적권을 사용하는 방법은 어렵지 않다. PriorityQueue(우선순위큐)를 사용해 쉽게 풀 수 있다.
디펜스할 때마다 적들의 수를 PriorityQueue에 저장하고 무적권을 써야 할 때 PriorityQueue에서 적들 중 가장 인원이 많았던 그룹을 뽑아서 무적권을 쓰면 된다.