[백준 11286] 절댓값 힙 구현하기(C#)

문제

https://www.acmicpc.net/problem/11286

고민

우선순위 큐를 처음 써봤다... 

우선순위 큐는 2개의 인자를 받아서 서로 비교한다.

 PriorityQueue<int, int> queue = new PriorityQueue<int, int>();

위처럼 선언하고 queue.Enqueue(값, 우선순위)를 입력해주면, ICompare()를 상속받은 클래스가 호출되면서 정렬을 해준다. 즉, queue에 값과 우선순위를 Enqueue하는 순간 자동으로 정렬이 된다는 것이다.

 

예를들어 (2, 1), (4, -1)을 Enqueue하면 Dequeue 에서 4와 2가 순서대로 출력된다.

왜냐하면 두번째 인자가 우선순위라 값이 작을수록 먼저 정렬되기 때문이다.

 

정렬은 우선순위 큐가 해줄거니까.. 연산말 잘 하면 되겠다고 생각했다. 그리고 이 생각에서 문제가 발생한다.

바로 시간초과!!!

 PriorityQueue<int, (Math.Abs(int), int)> queue = new PriorityQueue<int, (Math.Abs(int), int>();
 // (Math.Abs(int), int)의 의미는? 절댓값으로 변경한 수를 우선순위로 하되 동일한 수가 나온다면 뒤에 오는 int인자로 재정렬 해달라는 의미
 // 간단하게 말해서 1번째 규칙 Math.Abs(int).. 2번째 규칙 int가 된다는 것이다.
 // 1번째 규칙이 이행되지 않으면 2번째 규칙으로 넘어가서 우선순위를 지정해준다.

기존에 위처럼 queue를 생성하고 바로 로직을 구성했다. 그랬더니 시간초과가 발생했다.

그래서 우선순위 계산하는 로직을 새로 만들어 지정해주기로 한다.

 

위에서 설명한 대로 Enqueue는 ICompare()를 상속받은 클래스의 비교하는 메서드를 실행한다. 그럼 내가 로직을 새로 만들어서 지정하려면? ICompare()를 상속받은 다른 클래스를 만들면 된다.

   class NewCompare : IComparer<int>
   {
       public int Compare(int x, int y)
       {
           int abs1 = Math.Abs(x);
           int abs2 = Math.Abs(y);

           if(abs1 == abs2 )
           {
               return x < y ? -1 : 1;
           }
           else
           {
               return abs1 - abs2;
           }
       }
   }

문제의 조건은 다음과 같다.

1. 절댓값이 동일하면, 더 작은 수를 출력하고

2. 그렇지 않으면 절댓값이 작은 순서대로 출력한다.

 

여기서 헷갈리면 안되는 것. Compare()는 Enqueue(값, 우선순위)를 각각 x, y로 받는 것이 아니다. queue에 존재하는 수의 우선순위를 x, y에 담아서 비교하는 것이다.

 

(**if문이 궁금하다면 댓글 달아주시거나 gpt돌려보세욥!)

PriorityQueue<int, int> queue = new PriorityQueue<int, int>(new NewCompare());

그리고 queue에서 새 로직을 반영해서 우선순위를 정렬할 수 있게 생성자 칸에 제작한 클래스를 담아주면 된다.

 

다음은 코드 전문이다.

코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace Algorithm
{
    internal class 절댓값_힙_구현하기
    { 
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine()); // 연산의 개수

            StringBuilder sb = new StringBuilder();


            PriorityQueue<int, int> queue = new PriorityQueue<int, int>(new NewCompare());



            for (int i = 0; i < N; i++)
            {
                int num = int.Parse(Console.ReadLine());

                if(num == 0)
                {
                    if(queue.Count == 0)
                    {
                        sb.AppendLine(0.ToString());
                    }
                    else
                    {
                        sb.AppendLine(queue.Dequeue().ToString());
                    }
                }
                else
                {
                    queue.Enqueue(num, num); // Compare에서 우선순위를 절댓값으로 변형 해주기 때문에 우선순위 인자에 num을 그대로 넣었습니다.
                }
            }
            
            Console.WriteLine(sb.ToString());
        }
    }

    class NewCompare : IComparer<int>
    {
        public int Compare(int x, int y)
        {
            int abs1 = Math.Abs(x);
            int abs2 = Math.Abs(y);

            if(abs1 == abs2 )
            {
                return x < y ? -1 : 1;
            }
            else
            {
                return abs1 - abs2;
            }
        }
    }
}

이렇게 오래 걸리다니^^;;

지금까지 자료구조를 선언하고 제일 뒤에오는 (괄호)에 습관적으로 클래스를 담았는데, 정확한 의미는 모르고 있었다... (괄호)는 생서자 위치이며, 해당하는 객체(인스턴스)를 통해 로직을 수행합니다.

 

자료구조마다 원하는 객체(인스턴스)가 다르니 공식문서를 참고하는 것이 좋겠습니다.