주녘공부일지

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

카테고리 없음

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

주녘 2024. 5. 22. 19:44
728x90

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

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

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

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

 

풀이 순서

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

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

 

우선순위 큐 ( Priority Queue )

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

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

https://godgjwnsgur7.tistory.com/198

 

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

DataClass PriorityQueue // 데이터 추가해서 사용 public class DataClass { public int cost; public DataClass(int cost) { this.cost = cost; } } // DataClass의 cost를 기준으로 가장 작은 값을 우선으로 두는 우선순위 큐 public clas

godgjwnsgur7.tistory.com

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

 

풀이 순서

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;
    }
}
728x90
저작자표시