(Java) 프로그래머스 - 디펜스 게임

입력값이 매우 큰 편이었기 때문에 O(n) 이내에 끝내야겠다는 생각을 했다.

처음에는 내림차순으로 정렬을 하고 k를 우선적으로 사용하고, 나머지는 n을 사용하는 로직을 생각했다가

잘못된 로직이라는 것을 깨닫고 우선순위 큐를 이용하여 풀었다.

어떻게 생각하냐에 따라 엄청 간단한 문제일 수도 있지만, 내가 배배 꼬아서 생각했던지 풀이에 오랜 시간이 걸렸다.

---

로직

먼저 enemy 배열을 순회하며 n을 빼주고 우선순위 큐에 삽입한다.

만약 n이 음수로 내려간다면, 지금까지 지나왔던 라운드에 가장 큰 값이 우선순위 큐에 첫 번째 값으로

들어 있으니 그 값을 빼서 다시 n에 더해준다.

이렇게 하면 지나온 라운드 중 가장 큰 값에만 무적권을 쓰게 된 것과 같다.

더 이상 쓸 수 있는 무적권이 없다면 순회를 종료하면 된다.

 

최종 코드

import java.util.*;

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++) {
			n -= enemy[i];
			pq.add(enemy[i]);

			if (n < 0) {
				if (k > 0) {
					n += pq.poll();
					k--;
				} else {
					break;
				}
			}
			answer++;
		}
		return answer;
	}
}