C# 코딩테스트 강좌, 절댓값 힙 구현하기

안녕하세요, 여러분! 오늘은 절댓값 힙을 구현하는 문제를 해결해 보겠습니다. 알고리즘 문제를 풀고, 그 과정에서 C#의 기능을 활용해 보겠습니다. 앞서 언급한 ‘절댓값 힙’은 힙 구조를 이용하여 절댓값을 기준으로 정렬되는 특수한 힙입니다. 이 문제는 알고리즘 문제에서 자주 등장하는 주제입니다.

문제 설명

절댓값 힙은 다음과 같은 기능을 지원합니다:

절댓값이 가장 작은 수를 삭제하고 그 숫자를 출력한다.
절댓값이 같을 경우, 실제 값이 작은 수를 우선하여 삭제하고 출력한다.
새로운 정수를 추가한다.

예를 들어, 다음과 같은 작업을 수행할 수 있습니다:

1. 삽입: 3
2. 삽입: -1
3. 삽입: -2
4. 삭제

위 작업의 결과로 삭제되는 값은 -1이 됩니다. 이를 종합하여 풀어야 할 문제는 다음과 같습니다:

문제

절댓값 힙 기능을 구현하라. N개의 연산이 주어지고, 각각의 연산에 대해 알맞은 출력을 하도록 하라.

입력으로는 여러 개의 정수가 주어지며, 각 정수는 다음의 세 가지 연산을 의미한다:

0: 절댓값 힙에서 절댓값이 가장 작은 수를 삭제하고 출력한다.

X: 정수 X를 절댓값 힙에 삽입한다.

입력 및 출력

입력

첫 번째 줄에 연산의 개수 N이 주어집니다. (1 ≤ N ≤ 100,000)

그 다음 N줄에 걸쳐 연산이 주어집니다. 각 연산은 X (-1,000,000 ≤ X ≤ 1,000,000) 또는 0입니다.

출력

삭제된 숫자를 한 줄에 하나씩 출력한다. 삭제할 수 있는 숫자가 없는 경우 0을 출력해야 합니다.

문제 풀이

이제 문제를 해결하기 위한 C# 코드를 작성해 보겠습니다. 본 문제에서는 Priority Queue를 사용하여 절댓값 힙을 구현할 수 있습니다.

우선순위 큐(Heap) 설명

우선순위 큐는 각 요소가 우선 순위를 가지고, 이 경우 힙 구조를 사용합니다. C#에서는 SortedSet 또는 PriorityQueue를 사용하여 쉽게 구현할 수 있습니다.

C# 코드 구현

아래는 절댓값 힙을 구현한 C# 코드입니다:


using System;
using System.Collections.Generic;
using System.Linq;

class AbsoluteHeap
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var pq = new SortedSet<(int absolute, int value)>();

        for (int i = 0; i < n; i++)
        {
            int x = int.Parse(Console.ReadLine());
            if (x == 0)
            {
                if (pq.Count == 0)
                {
                    Console.WriteLine(0);
                }
                else
                {
                    var min = pq.First();
                    pq.Remove(min);
                    Console.WriteLine(min.value);
                }
            }
            else
            {
                pq.Add((Math.Abs(x), x));
            }
        }
    }
}

코드 설명

위 코드는 절댓값 힙을 구현하는 간단한 방법을 보여줍니다. 주요 단계는 다음과 같습니다:

입력 받기: 첫째 줄에서 연산의 개수 N을 읽고, 그 다음 줄부터 N개의 연산을 반복하여 처리합니다.
우선순위 큐 초기화: SortedSet를 사용하여 아래와 같은 tuple을 저장합니다: (절댓값, 실제 값). 여기서 절댓값을 기준으로 정렬하며, 절댓값이 동일할 경우 실제 값으로 정렬합니다.
연산 처리: 각 연산을 처리하면서 x가 0인 경우 (삭제 연산)는 SortedSet에서 최솟값을 삭제하고 출력합니다. 값이 존재하지 않으면 0을 출력합니다. x가 0이 아닌 경우, 절댓값과 실제 값을 튜플 형태로 추가합니다.

효율성

이 알고리즘은 로그 복잡도로 절댓값을 기준으로 입력값을 저장하고 삭제합니다. 따라서 복잡도는 O(N log N)입니다. 대부분의 경우, 이 정도의 시간 복잡도는 입력 제한에 부합할 것입니다.

결론

이번 포스팅에서는 절댓값 힙을 구현하는 방법에 대해 배웠습니다. C#의 특징인 SortedSet을 활용하여 마주치는 문제를 효율적으로 해결할 수 있음을 알 수 있습니다. 알고리즘 문제를 풀 때는 문제의 요구사항을 잘 읽고, 적절한 자료구조를 선택하는 것이 중요합니다. 다음 시간에도 흥미로운 알고리즘 문제로 찾아뵙겠습니다!