[프로그래머스] 디펜스 게임(JAVA)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/142085

---

 

풀이(17분)

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;
	}
}

 

처음에 조금 헤매었지만 풀이의 사고과정은 간단하다.

내가 이 작업을 한다면 어떻게 해야 할까?

(이때 중요한 것은 사람의 사고의 흐름을 컴퓨터는 하지 못하기 때문에 순서대로!!라는 것만 주의하여 생각해 보자.)

 

일단 진행을 하다가 만약 n이 부족해지고, k가 남아있다면? 

-> 지나온 것 중에 가장 큰 것을 다시 더해버리고 무적권을 쓴 것으로 하자!

 

그렇기 때문에 일단 n에서 빼면서 우선순위 큐에 넣어주자.

그 후 n이 음수가 되고, k(무적권)가 남아있다면 다시 n에 더해주고 k를 소모하자.

이렇게 하면 지나온 것 중 가장 큰 것들만 사용하여 진행할 수 있다!