프로그래머스 디펜스 게임 Kotlin (우선순위 큐)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/142085

프로그래머스

문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 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라운드까지 막을 수 있습니다.

풀이

풀이를 알아내기까지 흐름은 다음과 같다.

완탐 가능할까? 불가

백트래킹 가지치기..? 불가

dp, 누적 합, 이분 탐색?  모두 적합하지 않은 것 같다.

다른 접근이 필요해 보인다.

해서 떠오른 게 우선순위 큐다.

 

우선 enemy를 순차적으로 탐색해야 한다.

그중에 k개의 무적권을 효율적으로 사용해야 하는데 어떻게??

일단 enemy를 순회하면서 n보다 작으면 일단 들고간단 마인드.

sum에 더하고 내림차순 pq에 넣어주는 것으로 일단 들고간다.

그러다가 sum + enemy[i]가 n보다 큰 경우는??

무적권이 남은 경우 무적권을 써서 처리할 수 있다.

무적권이 남지 않은 경우 그대로 종료.

 

근데 어떤 놈을 처리해야 할까? 이번에 만난 enemy[i]? 아니면 전에 들고 가던 enemy[0~ i-1]중에 하나?

그렇다. 우리는 enemy[0 ~ i-1]중에 무엇을 뺄지 정하기 위해 우선순위 큐를 사용했다.

입력 예제에서 4,2까지 처리했다고 하자. 그럼 현재 상태는

sum = 6
pq = [4,2]
enemy[i] = 4 //3번째 적
무적권 사용 갯수 : 0
처리한 판의 개수 : 2

일단 무적권을 사용해야 함은 분명하고,

enemy[i]와 우선순위 큐의 가장 위의 값을 비교하여 더 큰 enemy를 제거하면 된다.

그럼 상태가 다음과 같이 바뀐다.

sum = 6 // 4를 빼고 다시 4를 넣었다.
pq = [4,2] //4를 빼고 다시 4를 넣었다.
enemy[i] = 5
무적권 사용 개수 : 1
처리한 판의 개수 : 3

자 이제 5를 만났을 때는?

sum = 7 // 4를 빼고 5를 넣었다.
pq = [5,2] // 4를 빼고 5를 넣었다.
enemy[i] = 3
무적권 사용 개수 : 2
처리한 판의 개수 : 4

 

핵심은 이렇다.

- 현재까지 적 + 다음 만날 적 > n인 경우

  - 무적권이 남은 경우

     - pq가 비어있거나 다음에 만날 적이 pq의 top보다 큰 경우

         - 다음에 만날 적에 무적권 사용

     - pq가 비어있지 않고 다음에 만날 적보다 pq의 top이 더 큰 경우

         - pq가 비지 않을 동안, 무적권이 남을 동안, 현재까지 적 + 다음 만날 적 > n인 동안 sum과 pq의 top을 빼주면서 무적권을 사용

  - 무적권이 없는 경우

     - 종료 

- 현재까지 만난 적 + 다음에 만날 적 < n인 경우

  - 그냥 sum과 pq에 추가 (라운드 처리 횟수 증가)

 

이후 무적권 사용 횟수 + 처리한 적의 횟수를 출력하면 된다.

코드

import java.util.*
class Solution {
    fun solution(n: Int, k: Int, enemy: IntArray): Int {
        val pq = PriorityQueue<Int> { a, b -> b - a }
        var sum = 0
        var cnt = 0
        var kCnt = 0
        for (ene in enemy) {
            if (sum + ene > n) {
                if (kCnt >= k) break
                if (pq.isEmpty() || ene > pq.peek()) {
                    kCnt++
                } else {
                    while (kCnt < k && pq.isNotEmpty() && sum + ene > n) {
                        sum -= pq.poll()
                        kCnt++
                    }
                    sum += ene
                    pq.add(ene)
                }
            } else {
                sum += ene
                cnt++
                pq.add(ene)
            }
        }
        return cnt + kCnt
    }
}