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

문제번호: 1655

문제명: 가운데를 말해요

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

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

오늘은 중앙값 구하기 문제를 풀었습니다. 매번 입력이 주어지는 수로 현재의 중앙값을 출력하는 문제입니다.
매번 입력이 주어질때마다 리스트를 정렬하면 시간초과가 발생하게 됩니다. 따라서 항상 정렬상태를 유지할 수 있는 최소 힙을 사용해야합니다.

 

그런데 또 문제가 있습니다. 최소힙은 인덱스 기반 접근이 불가능하다는 점 입니다. 따라서 minHeap, maxHeap힙 2개를 만들었습니다. minHeap에는 큰 값들을, maxHeap에는 작은 값들을 넣을것입니다. 그리고 maxHeap의 Peek에는 항상 중앙값이 나오도록 하였습니다.

이후에 Add메서드로 두 힙의 균형을 맞추면서 추가해주고 값이 뒤틀릴경우 재정렬 해주는 기능도 추가하였습니다.
다음은 정답코드입니다.

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

    int n = int.Parse(sr.ReadLine()!);

    PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>(); // 큰값들
    PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>(); // 작은값들, peek가 항상 중앙값이 됨

    for (int i = 0; i < n; i++)
    {
        Add(int.Parse(sr.ReadLine()!));
        sw.WriteLine(maxHeap.Peek());
    }

    void Add(int x)
    {
        if (maxHeap.Count == minHeap.Count)
            maxHeap.Enqueue(x, -x);
        else
            minHeap.Enqueue(x, x);

        if (minHeap.Count > 0 && maxHeap.Peek() > minHeap.Peek()) // 순서가 깨졌는지 검사한다.
        {
            int a = maxHeap.Dequeue();
            int b = minHeap.Dequeue();

            maxHeap.Enqueue(b, -b);
            minHeap.Enqueue(a, a);
        }
    }
}