문제
https://school.programmers.co.kr/learn/courses/30/lessons/142085
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제 개요
디펜스 게임은 준호가 병사 n명으로 적의 공격을 막는 게임입니다. 게임의 규칙은 다음과 같습니다:
- 병사 소모: 매 라운드마다 enemy[i]마리의 적이 등장하며, 이를 막기 위해 enemy[i]명의 병사가 소모됩니다.
- 병사 부족 시 게임 종료: 만약 남은 병사 수가 등장한 적의 수보다 적다면 게임은 종료됩니다.
- 무적권 사용: 무적권을 사용하면 병사를 소모하지 않고 한 라운드를 막을 수 있습니다. 무적권은 최대 k번 사용할 수 있습니다.
- 목표: 무적권을 적절히 사용하여 최대한 많은 라운드를 진행하는 것입니다.
입력으로는 병사의 초기 수 n, 무적권 사용 횟수 k, 매 라운드마다 등장하는 적의 수 배열 enemy가 주어집니다. 이를 기반으로 준호가 막을 수 있는 최대 라운드 수를 구해야 합니다.
접근 방법
- 우선순위 큐를 활용한 최대 적 병력 추적:
- 매 라운드 적의 병력을 추적하기 위해 우선순위 큐(Priority Queue)를 사용합니다.
- 병사가 부족한 상황(n < 0)이 발생하면, 지금까지 마주한 적들 중 가장 큰 병력을 무적권으로 처리하여 병사의 소모를 줄입니다.
- 병력 감소 및 무적권 사용:
- 각 라운드에서 n에서 적의 병력(enemy[i])을 차감합니다.
- 차감 후 병사가 부족할 경우:
- 무적권(k)이 남아 있다면, 큐에서 가장 큰 병력을 꺼내(poll) 무적권으로 처리하고 병력을 복구합니다.
- 무적권이 없다면, 더 이상 방어할 수 없으므로 현재 라운드 번호를 반환합니다.
- 모든 라운드 방어 가능 여부:
- 모든 라운드를 방어할 수 있는 경우, enemy 배열의 길이를 반환합니다.
import java.util.*;
class Solution {
public int solution(int n, int k, int[] enemy) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < enemy.length; i++) {
n -= enemy[i];
pq.offer(enemy[i]);
if (n < 0) {
if (k > 0) {
n += pq.poll(); // 가장 큰 적의 병력을 복구
k--;
} else {
return i; // 더 이상 방어 불가
}
}
}
return enemy.length; // 모두 방어 가능
}
}
'문제 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 가장 큰 정사각형 찾기 - Java (0) | 2024.11.22 |
---|---|
[프로그래머스] 리코쳇 로봇 - Java (0) | 2024.11.22 |
[프로그래머스] [PCCE 기출문제] 10번 / 데이터 분석 - Java (0) | 2024.11.22 |
[프로그래머스] [PCCP 기출문제] 2번 / 석유 시추 - Java (0) | 2024.11.21 |
[프로그래머스] 혼자 놀기의 달인 - Java (1) | 2024.11.20 |