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

문제번호: 1927

문제명: 최소 힙

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

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

 

골드달성 🥳🥳🥳

 

문제를 읽고 힙에서 최소 숫자를 힙이 아닌 최솟값을 효율적으로 삽입/삭제하기 위한 리스트를 이용하여 문제를 풀어보면 어떨까라라는 생각을 하여 시도해보았지만 3%에서 시간초과로 실패하고 말았습니다. 그래서 다른 자료구조를 찾아보게 되었는데 문제 제목 그대로 최소 힙(priority queue)이라는 자료구조가 있었습니다.

 

Priority Queue란, 우선순위가 높은 값이 먼저 나오는 자료구조입니다. PQ는 (최소힙일때)내부적으로 이진트리로서 작동합니다.

다음은 새 값이 추가되었을때 내부적으로 작동하는 과정입니다.

1. 새 값을 배열 맨 뒤에 추가한다.

2. 부모보다 값이 작다면 위로 교환 반복.

 

2를 삽입하기 전

2를 삽입한 후

 

다음은 정답코드입니다.

+ priority queue에는 이진트리가 가장 일반적이지만 다른 구현방법도 여러가지가 잇다고 합니다.

 

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

    int n = int.Parse(sr.ReadLine());
    PriorityQueue<int, int> queue = new();

    for (int i = 0; i < n; i++)
    {
        int input = int.Parse(sr.ReadLine()); // 입력받기
        if (input == 0) // 0이 들어왔을 때
        {
            if (queue.Count > 0) // 리스트 개수가 0 초과라면
            {
                sw.WriteLine(queue.Dequeue()); // 최소값 출력
            }
            else
            {
                sw.WriteLine(0);
            }
        }
        else
        {
            queue.Enqueue(input, input);
        }
    }

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