[프로그래머스 C#] Lv.2 디펜스 게임

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

무적권을 적절히 활용하여 가장 많은 스테이지를 클리어 할 수 있는 경우를 구하는 문제

- 스테이지는 0번 인덱스 스테이지부터 순서대로 진행되야 함

 

풀이 순서

1) 무적권을 쓰지 않고 클리어 한 스테이지 정보를 담으며 스테이지를 진행

2) 스테이지를 클리어 할 수 없다면, 무적권을 쓰지 않고 클리어 한 스테이지 중 가장 몬스터가 많은 스테이지에서 무적권을 사용함 처리 (이 때, 무적권이 없다면 더 이상 스테이지를 클리어 할 수 없음)

 

우선순위 큐 ( Priority Queue )

+ 처음엔 리스트로 하여 무적권을 사용할 때마다 리스트 정렬을 했으나 시간 초과 ( 범위가 아주 큼 )

 -> 우선순위 큐를 직접 구현해야 함 ( .NET 7.0 버전부터 우선순위 큐를 지원 )

https://godgjwnsgur7.tistory.com/198

[C# Reference] 우선순위 큐 ( Priority Queue )

+ 링크에 있는 우선순위 큐는 최소 값을 우선으로 두기 때문에 최대 값을 우선으로 두게 수정하여 사용해야 합니다.

 

풀이 순서

using System;
using System.Collections.Generic;

public class Solution
{
    // 우선순위 큐를 직접 구현하여 사용해야 함 (.NET 7.0 버전부터 사용 가능)
    public class PriorityQueue<T> where T : IComparable<T> { ... }

    public int solution(int n, int k, int[] enemy)
    {
        int answer = 0; // 스테이지 클리어 수
        var pq = new PriorityQueue<int>(); // 무적권 없이클리어 한 스테이지
        
        for (int i = 0; i < enemy.Length; i++)
        {
            // 스테이지 진행
            pq.Enqueue(enemy[i]);
            n -= enemy[i];

            // 스테이지 클리어 불가능
            if (n < 0)
            {
                // 무적권 사용
                if (k > 0)
                {
                    n += pq.Dequeue();
                    k--;
                }
                else
                    break;
            }

            // 스테이지 클리어 확인
            answer++;
        }

        return answer;
    }
}