[Kotlin] 99 클럽 코딩 테스트 스터디 미들러 38일차 - 디펜스 게임

https://school.programmers.co.kr/learn/courses/30/lessons/142085?language=kotlin

프로그래머스

[문제]

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

• 준호는 처음에 병사 n명을 가지고 있습니다.
• 매 라운드마다 enemy [i] 마리의 적이 등장합니다.
• 남은 병사 중 enemy[i]명 만큼 소모하여 enemy [i] 마리의 적을 막을 수 있습니다.
• 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
• 무적권은 최대 k번 사용할 수 있습니다.

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

 

[제한 사항]

 

[입출력 예]

 

[풀이]

해당 문제는 그리디 알고리즘을 통해 풀 수 있는 문제입니다.

그리디 알고리즘은 매 순간 최적이라고 생각되는 선택을 하는 알고리즘입니다.

모든 하위 단계에서도 최적을 선택하면 전체 문제 또한 최적의 계산이 가능합니다.

 

위 문제는 결국 가장 대미지가 큰 enemy를 무적권을 통해 방어하는 것이 일단 가장 큰 이득인 상황이라고 볼 수 있겠습니다. 

하지만 라운드 순서가 정해져 있기 때문에 그 순서를 당장 큰 값부터 처리하도록 재정렬 할 수 없으니

일단 병사들을 활용하여 차례대로 계산을 해줍니다. 그리고 계산된 적에 대해서는 우선순위 큐에 저장합니다.

fun solution(n: Int, k: Int, enemy: IntArray): Int {
    var soldiers = n
    var items = k
    //라운드별로 병사를 통해 막은 적의 수를 저장하는 큐
    val heap = PriorityQueue<Int>(compareByDescending { it })
.....

우선순위 큐는 삽입 순서와 상관없이 오름, 내림차순 정렬이 가능하니 Task 시간 상에서도 매우 유용합니다.

 

병사 값이 적의 대미지 값 이상이라면 병사들을 통해 적을 처리하고, 처리한 적을 큐에 삽입합니다.

for (i in enemy.indices) {
    val target = enemy[i]
    if (soldiers >= target) { //적의 데미지만큼 차감
        soldiers -= target
        heap.offer(target)
        .....

만일 병사가 상대할 수 없다면 현재 큐가 비어있거나 Peek 요소가 지금 상대해야 하는 적의 대미지보다 크다면
(Poll 요소 - 지금 상대 대미지)만큼 에너지를 돌려받습니다.
그리고 지금 상대하던 적을 Poll 한 요소를 대신하여 큐에 Offer 합니다.

이후에 무적권의 개수를 차감하는 것도 잊지 맙시다.

if (items > 0) {
    if (heap.isNotEmpty() && heap.peek()!! > target) {
        soldiers += heap.poll()!! - target
        heap.offer(target)
    }
    items --
} else {
    return i
}

아이템이 없다면 이제 어떻게 처리할 방도가 없으므로 진행 카운트만큼 반환해 주면 됩니다.
이 모든 케이스가 필요 없는 상황에서는 기본 값인 enemy.size를 반환해 주면 됩니다.

 

아래는 코틀린 전체 코드입니다.

fun solution(n: Int, k: Int, enemy: IntArray): Int {
    var soldiers = n
    var items = k
    //라운드별로 병사를 통해 막은 적의 수를 저장하는 큐
    val heap = PriorityQueue<Int>(compareByDescending { it })

    for (i in enemy.indices) {
        val target = enemy[i]
        if (soldiers >= target) { //적의 데미지만큼 차감
            soldiers -= target
            heap.offer(target)
        } else {
            if (items > 0) {
                if (heap.isNotEmpty() && heap.peek()!! > target) {
                    soldiers += heap.poll()!! - target
                    heap.offer(target)
                }
                items --
            } else {
                return i
            }
        }
    }
    return enemy.size
}