백준 C# - 11286 +) 눈물의 풀이

들어가기 앞서

풀다가 못풀겠어서 힌트를 찾아봤는데 C#으로된 정답 코드가 없었다.. Phthon으로 된 코드는 heapq을 이용해서 코드가 간단한데 C#은 없다 눈물.. 그래서 6시간정도 걸렸다. 하핳.. 그래도 통과돼서 뿌듯하다

 

실패 01 Sort 사용

첫번째로 풀었을때 Sort를 이용해서 풀었는데 2%에서 시간초과가 떴다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace baek2
{
    class Program
    {
        public static void Main()
        {
            List<Tuple<int,int>> pq = new List<Tuple<int,int>>();
            int n = int.Parse(Console.ReadLine());

            for(int i = 0; i<n; i++)
            {
                int input = int.Parse(Console.ReadLine());
                if (input == 0 && pq.Count == 0)
                {
                    Console.WriteLine(input);
                }
                else if (input == 0 && pq.Count != 0)
                {
                    pq.RemoveAt(0);
                }
                else
                {
                    pq.Add(Tuple.Create(Math.Abs(input), input));
                    pq.Sort();
                }
            }
        }
    }
}

---

실패 02  IComparer 사용

시간초과가 뜨고 effective C#에서 봤던 IComparer가 생각났다. 그리고 또 제출을 해봤는데 똑같이 2%에서 시간초과가 떴다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace baek2
{
    class Program
    {
        public static void Main()
        {

            List<Tuple<int, int>> pq = new List<Tuple<int, int>>();
            int n = int.Parse(Console.ReadLine());

            for (int i = 0; i < n; i++)
            {
                int input = int.Parse(Console.ReadLine());
                if (input == 0 && pq.Count == 0)
                {
                    Console.WriteLine(input);
                }
                else if (input == 0 && pq.Count != 0)
                {
                    Console.WriteLine(pq[0].Item2);
                    pq.RemoveAt(0);                  
                }
                else
                {
                    pq.Add(Tuple.Create(Math.Abs(input), input));
                    pq.Sort(new Comparer());
                }
            }

        }
        class Comparer : IComparer<Tuple<int, int>>
        {
            public int Compare(Tuple<int, int> a, Tuple<int, int> b)
            {
                if (Math.Abs(a.Item1) == Math.Abs(b.Item1)) // 첫번째 요소가 같은 경우 두 번째 요소 비교
                    return a.Item2.CompareTo(b.Item2); 
                else
                    return Math.Abs(a.Item1).CompareTo(Math.Abs(b.Item1));  // 첫번째 요소 비교
            }
        }
    }
}

---

실패 03 고민의 시간

여기에서 이제 C#의 Priority Queue에 관해서 구글링을 해봤는데 존재하긴 했다. 하지만 .NET Framework에 포함되어있지 않고 따로 외부라이어리를 다운로드 받아서 사용해야 했다.

public class PriorityQueue<TElement,TPriority>

그리고 더 찾아보다가 SortedSet과 SortedDictonary를 찾았다. 이 클래스를 사용하면 요소가 정렬된 순서로 유지된다. 그러므로 PriorityQueue와 비슷한점이 있어서 이를 사용해서 풀어야겠다고 생각이들었다.

실패 04 SortedDictonary 사용

SortedDictonary를 사용하면 금방 풀릴줄 알았는데 가장 큰 특징인 Key가 중복값을 가질 수 없다는 점이 발목을 잡았다. 그래서 기존의 알고리즘을 싹 바꿔야 했다.

---

정답 알고리즘

그래서 생각해낸 아이디어가 Value에 같은 Key값을 가진 애들을 Count하는 거였다.

01 0이외의 값이 입력되는 경우

해당 Key값이 있었는지 확인하고 존재했으면 Value값을 1증가시키고 아닌 경우 Add한다.

if (pq.ContainsKey(input))
{
    pq[input]++;
}
else
{
    pq.Add(input, 1);
}

2) 0이 입력되는 경우

정답의 Key값을 가져오고 Value값을 확인한 후 만약 1보다 큰 경우 Value값을 1감소시키고 1보다 작은 경우 해당 Key값을 제거 한다.

else if (input == 0 && pq.Count != 0)
{
    int minValue = pq.First().Key;
    sb.AppendLine(minValue.ToString());
    if (pq[minValue] > 1)
    {
        pq[minValue]--;
    }
    else
    {
        pq.Remove(minValue);
    }
}

---

실패 02 vs 정답 알고리즘 실행시간 비교

실패 02인 경우 List는 정렬된 상태를 유지하고 있지 않아서 요소를 추가한 후 명시적으로 Sort메서드를 호출해야 정렬한다. 그러므로 입력 크기에 따라 작업 시간이 증가한다.

정답 알고리즘의 경우 SortedDictionary는 내부적으로 키를 기준으로 정렬된 상태를 유지한다. 그러므로  요소를 추가할 때마다 정렬 작업을 따로 수행할 필요가 없다. 따라서 입력 크기에 따라 작업에 걸리는 시간이 증가하지 않는다.

 

---

코드 전문

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace baek2
{
    public class Comparer : IComparer<int>
    {
        public int Compare(int x, int y)
        {
            int absX = Math.Abs(x);
            int absY = Math.Abs(y);

            if (absX == absY)
            {
                return x.CompareTo(y);
            }
            return absX.CompareTo(absY);
        }
    }
    class Program
    {
        public static void Main()
        {
            SortedDictionary<int, int> pq = new SortedDictionary<int, int>(new Comparer());

            StringBuilder sb = new StringBuilder();
            int n = int.Parse(Console.ReadLine());

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

                if (input == 0 && pq.Count == 0)
                {
                    sb.AppendLine("0");
                }
                else if (input == 0 && pq.Count != 0)
                {
                    int minValue = pq.First().Key;
                    sb.AppendLine(minValue.ToString());
                    if (pq[minValue] > 1)
                    {
                        pq[minValue]--;
                    }
                    else
                    {
                        pq.Remove(minValue);
                    }
                }
                else
                {
                    if (pq.ContainsKey(input))
                    {
                        pq[input]++;
                    }
                    else
                    {
                        pq.Add(input, 1);
                    }
                }
            }
            Console.Write(sb);
        }
    }
}