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

문제번호: 2696

문제명: 중앙값 구하기

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

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

 

오늘은 중앙값 구하기 문제를 풀었습니다. 기본 로직은 어제 풀이했었던 '가운데로 말해요'와 거의 동일합니다.
https://bimtaeur30.tistory.com/116

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

최소 힙을 사용하여 중앙값을 구할 수 있는 로직을 사용하였고 자세한 내용은 위 블로그를 참고 바랍니다.
여튼 이 로직을 사용하여 문제에 맞게 각 테스트케이스마다 중앙값을 출력해주었습니다.

다음은 정답코드입니다.

 

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

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

    for (int i = 0; i < n; i++)
    {
        PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>(); // 큰 값들
        PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>(); // 작은 값들

        void Add(int x)
        {
            if (maxHeap.Count == minHeap.Count)
                maxHeap.Enqueue(x, -x); // maxHeap처럼 사용
            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);
            }
        }

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

        // 여러 줄에 걸친 입력 처리
        List<int> nums = new List<int>();
        while (nums.Count < nn)
        {
            string[] parts = sr.ReadLine()!.Split();
            foreach (var p in parts)
                nums.Add(int.Parse(p));
        }

        List<int> answer = new List<int>();

        for (int j = 0; j < nn; j++)
        {
            Add(nums[j]);

            if (j % 2 == 0) // 홀수번째 입력일 때 중앙값 출력
                answer.Add(maxHeap.Peek());
        }

        sw.WriteLine(answer.Count);

        for (int j = 0; j < answer.Count; j++)
        {
            sw.Write(answer[j] + " ");
            if ((j + 1) % 10 == 0)
                sw.WriteLine();
        }

        if (answer.Count % 10 != 0)
            sw.WriteLine();
    }
}