[C# / Lv3] 이중우선순위큐

 

 

 

 

 

풀이 코드

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string[] operations) {
        Heap heap = new Heap();
        for(int i = 0; i < operations.Length; i++)
        {
            string[] split = operations[i].Split(" ");
            if(split[0] == "I")
            {
                heap.Add(Int32.Parse(split[1]));
            }
            else
            {
                if(split[1] == "1")
                {
                    heap.RemoveMax();
                }
                else
                {
                    heap.RemoveMin();
                }
            }
        }
        int[] answer = heap.GetAnswer();
        return answer;
    }
}

public class Heap
{
    private List<int> m_minHeap = new List<int>();
    private List<int> m_maxHeap = new List<int>();

    public void Add(int n)
    {
        m_minHeap.Add(n);
        SortUp(m_minHeap, CompareMin);
        m_maxHeap.Add(n);
        SortUp(m_maxHeap, CompareMax);
    }

    public void RemoveMin()
    {
        if(m_minHeap.Count <= 0 || m_maxHeap.Count <= 0)
        {
            return;
        }

        m_minHeap[0] = m_minHeap[m_minHeap.Count - 1];
        m_minHeap.RemoveAt(m_minHeap.Count - 1);
        SortDown(m_minHeap, CompareMin);

        m_maxHeap.RemoveAt(m_maxHeap.Count - 1);
    }

    public void RemoveMax()
    {
        if(m_minHeap.Count <= 0 || m_maxHeap.Count <= 0)
        {
            return;
        }

        m_maxHeap[0] = m_maxHeap[m_maxHeap.Count - 1];
        m_maxHeap.RemoveAt(m_maxHeap.Count - 1);
        SortDown(m_maxHeap, CompareMax);

        m_minHeap.RemoveAt(m_minHeap.Count - 1);
    }

    public int[] GetAnswer()
    {
        int[] answer = new int[] { 0, 0 };
        if(m_maxHeap.Count > 0 && m_minHeap.Count > 0)
        {
            answer[0] = m_maxHeap[0];
            answer[1] = m_minHeap[0];
        }

        return answer;
    }

    private void SortDown(List<int> list, Func<int, int, int> compare)
    {
        int currentIndex = 0;
        while(true)
        {
            int leftIndex = currentIndex * 2 + 1;
            int rightIndex = currentIndex * 2 + 2;
            int swapIndex = currentIndex;

            if(leftIndex < list.Count)
            {
                swapIndex = leftIndex;

                if(rightIndex < list.Count)
                {
                    if(compare.Invoke(list[leftIndex], list[rightIndex]) < 0)
                    {
                        swapIndex = rightIndex;
                    }
                }

                if(compare.Invoke(list[currentIndex], list[swapIndex]) < 0)
                {
                    Swap(list, currentIndex, swapIndex);
                    currentIndex = swapIndex;
                }
                else
                {
                    return;
                }
            }
            else
            {
                return;
            }
        }
    }

    private void SortUp(List<int> list, Func<int, int, int> compare)
    {
        int currentIndex = list.Count - 1;
        int parentIndex = currentIndex / 2;
        while(true)
        {
            if(compare.Invoke(list[currentIndex], list[parentIndex]) > 0)
            {
                Swap(list, currentIndex, parentIndex);
                currentIndex = parentIndex;
                parentIndex = currentIndex / 2;
            }
            else
            {
                break;
            }
        }
    }

    private void Swap(List<int> list, int indexA, int indexB)
    {
        int tmp = list[indexA];
        list[indexA] = list[indexB];
        list[indexB] = tmp;
    }

    private int CompareMax(int a, int b)
    {
        return a.CompareTo(b);
    }

    private int CompareMin(int a, int b)
    {
        return -CompareMax(a, b);
    }
}

• 최소값을 루트에 갖는 List와 최대값을 루트에 갖는 List 2개를 만들어주고, 값이 들어가거나 빠질때마다 SortUp, SortDown으로 리스트를 갱신해준다.
• 최종 결과값은 최소 List와 최대 List의 루트값을 출력해주면 된다.

 

 

 

 

기타

- 문제 카테고리가 힙으로 분류되어있어서 힙을 구현해서 사용했다. (다른사람 풀이를 보니 Linq를 사용해서 짧게 작성했던데, 카테고리 생각하면 Linq사용하는게 정답같아보이지는 않는다.)

- 힙에 대한 설명은 아래 포스팅 참조

[C#] 자료구조 힙(Heap) 트리 구현