[프로그래머스] C# 문제풀이 31. 이중우선순위큐

---

https://programmers.co.kr/learn/courses/30/lessons/42628?language=csharp 

코딩테스트 연습 - 이중우선순위큐

---

문제 설명)

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어수신 탑(높이)

I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

제한사항)

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

입출력 예)

operations	return
["I 16","D 1"]	[0,0]
["I 7","I 5","I -5","D -1"]	[7,5]

---

먼저, minHeap과 maxHeap을 모두 가진 Heap 클래스를 구현합니다.

public class Heap
{
    public List<int> minHeap = new List<int>();
    public List<int> maxHeap = new List<int>();

    public Heap()
    {
        minHeap.Add(0);
        maxHeap.Add(0);
    }

    public void AddHeap(int num)
    {
        minHeap.Add(num);
        maxHeap.Add(num);
        if (minHeap.Count <= 2) return;
        int idx = minHeap.Count - 1;
        while (true)
        {
            if (idx == 1) break;
            if (minHeap[idx / 2] > minHeap[idx])
            {
                int temp = minHeap[idx];
                minHeap[idx] = minHeap[idx / 2];
                minHeap[idx / 2] = temp;
                idx = idx / 2;
            }
            else break;
        }
        idx = minHeap.Count - 1;
        while (true)
        {
            if (idx == 1) break;
            if (maxHeap[idx / 2] < maxHeap[idx])
            {
                int temp = maxHeap[idx];
                maxHeap[idx] = maxHeap[idx / 2];
                maxHeap[idx / 2] = temp;
                idx = idx / 2;
            }
            else break;
        }
    }

    public int HeapOut(bool is_Min)
    {
        int num = 0;
        if (minHeap.Count <= 1) return num;
        if (is_Min)
        {
            num = minHeap[1];
            minDown(1);
            maxDown(maxHeap.FindIndex(x => x == num));
        }
        else
        {
            num = maxHeap[1];
            maxDown(1);
            minDown(minHeap.FindIndex(x => x == num));
        }
        return num;
    }

    public void maxDown(int index)
    {
        maxHeap[index] = maxHeap[maxHeap.Count - 1];
        maxHeap.RemoveAt(maxHeap.Count - 1);
        int left, right, idx = index;
        while (true)
        {
            left = idx * 2;
            right = left + 1;
            if (left >= maxHeap.Count) break;
            else if (right == maxHeap.Count)
            {
                if (maxHeap[left] > maxHeap[idx])
                {
                    int temp = maxHeap[idx];
                    maxHeap[idx] = maxHeap[left];
                    maxHeap[left] = temp;
                }
                idx = left;
                break;
            }
            else
            {
                if (maxHeap[left] > maxHeap[right] && maxHeap[left] > maxHeap[idx])
                {
                    int temp = maxHeap[idx];
                    maxHeap[idx] = maxHeap[left];
                    maxHeap[left] = temp;
                    idx = left;
                }
                else if (maxHeap[left] <= maxHeap[right] && maxHeap[right] > maxHeap[idx])
                {
                    int temp = maxHeap[idx];
                    maxHeap[idx] = maxHeap[right];
                    maxHeap[right] = temp;
                    idx = right;
                }
                else break;
            }
        }
    }

    public void minDown(int index)
    {
        minHeap[index] = minHeap[minHeap.Count - 1];
        minHeap.RemoveAt(minHeap.Count - 1);
        int left, right, idx = index;
        while (true)
        {
            left = idx * 2;
            right = left + 1;
            if (left >= minHeap.Count) break;
            else if (right == minHeap.Count)
            {
                if (minHeap[left] < minHeap[idx])
                {
                    int temp = minHeap[idx];
                    minHeap[idx] = minHeap[left];
                    minHeap[left] = temp;
                }
                idx = left;
                break;
            }
            else
            {
                if (minHeap[left] < minHeap[right] && minHeap[left] < minHeap[idx])
                {
                    int temp = minHeap[idx];
                    minHeap[idx] = minHeap[left];
                    minHeap[left] = temp;
                    idx = left;
                }
                else if (minHeap[left] >= minHeap[right] && minHeap[right] < minHeap[idx])
                {
                    int temp = minHeap[idx];
                    minHeap[idx] = minHeap[right];
                    minHeap[right] = temp;
                    idx = right;
                }
                else break;
            }
        }
    }
}

 

operations 문자열을 Split(' ')으로 분리하고, 숫자 입력인지, 최대값/최소값 제거인지 구분해서 입력해줍니다.

public int[] solution(string[] operations)
{
    Heap heap = new Heap();
    for (int i = 0; i < operations.Length; i++)
    {
        string[] s = operations[i].Split(' ');
        if (s[0] == "I")
        {
            Console.WriteLine("추가:" + s[1]);
            heap.AddHeap(int.Parse(s[1]));
        }
        else if (s[0] == "D")
        {
            if (s[1] == "1") Console.WriteLine("최대:" + heap.HeapOut(false));
            else if (s[1] == "-1") Console.WriteLine("최소:" + heap.HeapOut(true));
        }
    }
    int[] answer = new int[2];
    if(heap.minHeap.Count <= 1)
    {
        answer[0] = 0;
        answer[1] = 0;
    }
    else
    {
        answer[0] = heap.maxHeap[1];
        answer[1] = heap.minHeap[1];
    }
    return answer;
}

---

풀이 링크 : GitHub