[C#] 백준 1417번 문제풀이

문제번호: 1417

문제명: 국회의원 선거

문제링크: https://www.acmicpc.net/problem/1417

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

 

오늘은 국회의원 선거라는 문제를 풀었습니다. 최소힙을 사용하여 문제를 풀었고 값이 클수록 우선순위를 높게 하여 자신의 투표율과 비교했을 때 같거나 크면 계속 1씩 빼주고 자신의 투표수에 1을 더하는 방식으로 문제를 풀었습니다. 처음엔 단순하게 리스트를 이용하여 문제를 풀었는데, 최댓값을 찾을 때마다 O(N) 시간이 걸리게 됨으로써 시간초과가 발생했습니다. 그래서 우선순위에 따라 최댓값이 가장 앞에 있음을 보장하기 위해 최소힙으로 자료구조를 교체하였습니다.

다음은 정답코드입니다.

 

public static void Main()
{
    using var sr = new StreamReader(Console.OpenStandardInput());
    using var sw = new StreamWriter(Console.OpenStandardOutput());

    int N = int.Parse(sr.ReadLine());
    int myVote = int.Parse(sr.ReadLine());

    if (N == 1)
    {
        sw.WriteLine(0);
        return;
    }

    var pq = new PriorityQueue<int, int>();

    for (int i = 0; i < N - 1; i++)
    {
        int vote = int.Parse(sr.ReadLine());
        pq.Enqueue(vote, -vote);
    }

    int count = 0;

    while (pq.Count > 0 && pq.Peek() >= myVote)
    {
        int maxVote = pq.Dequeue();
        maxVote--;
        myVote++;
        count++;

        pq.Enqueue(maxVote, -maxVote);
    }

    sw.WriteLine(count);

    sr.Close();
    sw.Close();
}