[11286] - 절댓값 힙

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

11286번: 절댓값 힙

접근 방법

1. 우선순위 큐에 절댓값을 씌워서 넣어주면 되는거 아닌가? -> 틀림 - 정렬이 되지 않아서

2. 사전으로 키를 절댓값 우선순위, 값을 리스트로 정렬해서 넣어주고 출력 -> 시간초과

3. 도저히 정렬 방법이 떠오르지 않아서 음수와 양수 우선순위 큐 2개 만듬 -> 성공

 

문제 풀이

정렬 방법이 떠오르지 않아 우선순위 큐 두개를 만들어서 풀었다.

• 입력이 0이 아니면 - 들어온 숫자의 부호에 맞게 양수, 음수 큐에 넣는데, priority는 양수로 넣어줌
• 입력이 0이면 - 일단 두 큐의 개수 확인
• 둘다 큐에 든게 있으면 두개의 peek를 비교하여 절댓값이 더 작은거 deque-출력
• 음수큐에만 든게 있으면 음수 큐 deque-출력
• 양수큐에만 든게 있으면 양수 큐 deque-출력
• 두 큐가 비었으면 0 출력

피드백

도무지 같은 우선순위 내 값을 정렬할 방법이 떠오르지 않았다. 다른 사람들의 풀이를 보니 우선순위^2에 음수면 -1, 양수면 그대로 두어서 푸는 방법이 있다는 것을 알게 되었다.

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

namespace Baekjoon.silver
{
    class _11286
    {
        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            int n = int.Parse(Console.ReadLine());
            //양수
            PriorityQueue<int,int> plus = new PriorityQueue<int,int>();
            //음수
            PriorityQueue<int,int> minus = new PriorityQueue<int,int>();

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

                if(num == 0)
                {
               		//양,음 둘다 값이 있으면
                    if (minus.Count > 0 && plus.Count > 0)
                    {
                    	//음수의 절댓값이 더 크면 양수꺼 출력
                        if (Math.Abs(minus.Peek()) > Math.Abs(plus.Peek()))
                            stb.AppendLine(plus.Dequeue().ToString());
                        //아니면 음수꺼 출력
                        else
                            stb.AppendLine(minus.Dequeue().ToString());
                    }
                    //음수만 값이 있으면 음수꺼 출력
                    else if (minus.Count > 0)
                        stb.AppendLine(minus.Dequeue().ToString());
                    //양수만 값이 있으면 양수꺼 출력
                    else if (plus.Count > 0)
                        stb.AppendLine(plus.Dequeue().ToString());
                    //둘다 없으면 0 출력
                    else
                        stb.AppendLine("0");
                }
                else
                {
                	//양수면 양수에, 음수면 음수에 넣기
                    if (num > 0)
                        plus.Enqueue(num, num);
                    else
                        minus.Enqueue(num, Math.Abs(num));
                }
            }

            Console.WriteLine(stb);
        }
    }
}