[프로그래머스][Kotlin] 디펜스 게임

해당문제는 PriorityQueue(우선 순위 큐)의 사용과 아이디어가 있다면 풀 수 있는 문제였습니다.
입력값 : 준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k , 의 수가 순서대로 담긴 정수 배열 enemy
예를 들어 n = 10, k = 2, enemy = [1,2,5,4,3,12,10] 로 입력 될 경우
첫번째 아이디어 : enemy에서 높은 숫자들에 무적권을 사용하자!
첫번째 아이디어로 작성할 경우 12,10에서 무적권을 사용하게 됩니다.
그렇다면 라운드는 1,2,5(총 3라운드)의 병사를 막고 무적권을 사용하지 못하여 3라운드 만을 진행할 수 있습니다.
해당 아이디어 로는 무적권을 사용하지 못하여 옳지 못한 아이디어라는 것을 알 수 있습니다.
그렇다면 다른 아이디어를 생각해봐야겠습니다.
첫번째 아이디어처럼 무적권을 사용하지 못하는 경우가 생기지 않도록 해야겠습니다.

두번째 아이디어: 무적권을 회복약처럼 생각하여 지나온 라운드 중에서 가장 큰 값을 조회하여 회복하자!
두번째 아이디어의 경우 첫번째 아이디어처럼 무적권을 사용하지 못하는 경우가 생기지 않을 것 같습니다.
입력값은 첫번재 아이디어와 동일하다고 가정하고 생각해 보겠습니다.

진행된 enemy : 1,2,5
현재 병사 : 10-1-2-5 = 2
다음 병사 : 4

여기서 무적권을 사용해야 한다면 4보다는 5에 쓰는 것이 더욱 효율적이라고 생각을 할 수 있습니다.
그렇다면 진행된 enemy내에서 가장 큰 값을 찾으려면 sort 기능을 사용하거나 maxOrNull() 함수를 사용할 수 있기도 하지만, 최대 1,000,000번을 해야될 수 있습니다. 그렇다면 O(n log(n))의 시간 복잡도를 가지게 되어 시간 초과가 날 것 같습니다.
그렇다면 저장 할 때부터 PriorityQueue를 사용하여 정렬을 한다면 어떤 시간 복잡도를 가지게 되는지 확인해 보겠습니다.

"우선순위 큐에서의 시간 복잡도는 삽입, 삭제 시 O(logN)의 시간이 걸린다." 라는 것을 알 수 있습니다.
그러면 라운드진행 마다 저장해놓고 sort를 하는 것보다 우선순위큐를 사용하여 지나온 라운드 별로 최대값을 조회 하는 것이 빠를 것 같다는 생각을 할 수 있습니다.

두번째 아이디어 처럼 추가 진행 할 경우
진행된 enemy : 1,2,5
현재 남은 병사 : 10-1-2-5 = 2
남은 무적권 : 2
다음 병사 : 4
--------------------------------------
진행된 enemy : 1,2,5
현재 병사 : 10-1-2-5(무적권 사용) = 7
남은 무적권 : 1
다음 병사 : 4
--------------------------------------
진행된 enemy : 1,2,5,4
현재 병사 : 10-1-2-5(무적권 사용)-4 = 3
남은 무적권 : 1
다음 병사 : 3
--------------------------------------
진행된 enemy : 1,2,5,4,3
현재 병사 : 10-1-2-5(무적권 사용)-4-3 = 0
남은 무적권 : 1
다음 병사 : 12
--------------------------------------
진행된 enemy : 1,2,5,4,3,12
현재 병사 : 10-1-2-5(무적권 사용)-4-3-12(무적권 사용) = 0
남은 무적권 : 0
다음 병사 : 10
다음 병사는 현재 남은 병사 보다 많고 무적권을 사용 할 수 없으므로 라운드 종료.
최종 라운드: 6라운드

아이디어 1과 비교하여 3라운드를 더 진행 할 수 있었습니다.
아이디어 2를 코드로 작성한다면 아래와 같은 코드로 작성 할 수 있습니다.

import java.util.Collections
import java.util.PriorityQueue
class Solution {
    fun solution(n: Int, k: Int, enemy: IntArray): Int {
        var answer: Int = 0
        var pq = PriorityQueue<Int>(Collections.reverseOrder())
        var N = n
        var K = k
        for(e in enemy){
            pq.add(e) // 우선순위큐에 라운드 별 병사수 저장
            N -= e // 일단 라운드 진행
            while(N < 0 && K > 0){ //라운드 진행 후 남은 병사가 0보다 작은 경우 와 무적권이 있을 때
                N += pq.poll() // 진행한 라운드중 가장 큰 값을 병사 회복
                K-- // 무적권 차감
            }
            if(N < 0) break // 무적권을 모두 사용하고, 병사가 0보다 작을 경우 for문 탈출(라운드 끝)
            answer++ // 라운드가 종료되지 않았다면 answer값 1증가(라운드 수 카운트)
        }
        return answer
    }
}

하기는 해당 코드 실행 결과 입니다.

테스트 1 〉	통과 (3.44ms, 60.8MB)
테스트 2 〉	통과 (3.37ms, 63.6MB)
테스트 3 〉	통과 (87.25ms, 111MB)
테스트 4 〉	통과 (7.47ms, 107MB)
테스트 5 〉	통과 (10.10ms, 62.2MB)
테스트 6 〉	통과 (105.93ms, 112MB)
테스트 7 〉	통과 (49.85ms, 112MB)
테스트 8 〉	통과 (19.79ms, 109MB)
테스트 9 〉	통과 (29.60ms, 109MB)
테스트 10 〉	통과 (66.82ms, 134MB)
테스트 11 〉	통과 (0.44ms, 107MB)
테스트 12 〉	통과 (1.26ms, 106MB)
테스트 13 〉	통과 (0.35ms, 62.1MB)
테스트 14 〉	통과 (0.52ms, 60.4MB)
테스트 15 〉	통과 (0.53ms, 62.2MB)
테스트 16 〉	통과 (0.49ms, 62MB)
테스트 17 〉	통과 (1.49ms, 58.6MB)
테스트 18 〉	통과 (0.51ms, 60.1MB)
테스트 19 〉	통과 (0.55ms, 59.6MB)
테스트 20 〉	통과 (0.36ms, 62.2MB)
테스트 21 〉	통과 (0.54ms, 61.6MB)
테스트 22 〉	통과 (0.37ms, 60.2MB)
테스트 23 〉	통과 (1.27ms, 59.1MB)
테스트 24 〉	통과 (0.66ms, 60.1MB)
테스트 25 〉	통과 (0.85ms, 60MB)
테스트 26 〉	통과 (1.23ms, 60.9MB)
테스트 27 〉	통과 (0.80ms, 59.9MB)
테스트 28 〉	통과 (0.64ms, 59MB)
테스트 29 〉	통과 (1.19ms, 60.5MB)
테스트 30 〉	통과 (3.43ms, 61.5MB)
테스트 31 〉	통과 (1.07ms, 58.4MB)
테스트 32 〉	통과 (1.26ms, 59.1MB)