<Lv.3> 이중우선순위큐 (프로그래머스 : C#)

https://school.programmers.co.kr/learn/courses/30/lessons/42628

📕 문제 설명

숫자 삽입, 최대값 삭제, 최솟값 삭제 기능을 가지는 이중 우선순위 큐를 구현해 operation들을 실행하고 비어 있지 않는 경우 [최대, 최소] 빈 경우 [0, 0] 반환하기

• Input
  operation 정보
• Output
  큐가 빈 경우 [0, 0], 아니면 [최대, 최소] 반환

예제

풀이

최대 최소 힙 만들어서 operation마다 어디서 빼낼지 결정하고 계속 처리하면 된다. Dequeue부분에서 count를 체크하고 시도하도록만 처리하면 아주 간단한 문제다.

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string[] operations) {
        PriorityQueue minHeap = new PriorityQueue();
        PriorityQueue maxHeap = new PriorityQueue();
        
        foreach(string operation in operations)
        {
            string[] currOperation = operation.Split(" ");
            string action = currOperation[0];
            int number = Int32.Parse(currOperation[1]);
            
            if (currOperation[0] == "I")
            {
                minHeap.Enqueue(-number);
                maxHeap.Enqueue(number);
                continue;
            }
            
            if (number == 1 && minHeap.Count > 0)
            {
                int currValue = maxHeap.Dequeue();
                minHeap.Remove(-currValue);
            }
            else if (number == -1 && minHeap.Count > 0)
            {
                int currValue = minHeap.Dequeue();
                maxHeap.Remove(-currValue);
            }
        }
        
        if (minHeap.Count == 0)
        {
            return new int[] {0, 0};
        }
        else
        {
            return new int[] {maxHeap.Dequeue(), -minHeap.Dequeue()};
        }
    }
}

public class PriorityQueue // MaxHeap
{
    private List<int> heap = new List<int>();

    public int Count => heap.Count;
    
    public void Enqueue(int data)
    {
        heap.Add(data);
        int now = heap.Count - 1; // 추가한 노드 위치 (트리 마지막 레벨 왼쪽)
        
        while (now > 0) // 순서 지정하기
        {
            int next = (now - 1) / 2; // 부모 노드 (트리)
            if (heap[now] < heap[next]) break;
            // 부모노드보다 추가한게 크면 Swap
            int temp = heap[now];
            heap[now] = heap[next];
            heap[next] = temp;
            now = next;
        }
    }
    
    public int Dequeue()
    {
        int ret = heap[0]; // return할 값 (트리 root에 max 저장해둔 형태)
        int lastIndex = heap.Count - 1;
        heap[0] = heap[lastIndex];
        heap.RemoveAt(lastIndex);
        lastIndex -= 1;
        int now = 0;
        
        while (true)
        {
            int left = 2 * now + 1;
            int right = 2 * now + 2;
            int next = now;
            
            if (left <= lastIndex && heap[next] < heap[left]) next = left; // 왼쪽보다 작으면 왼쪽으로 보내기
            if (right <= lastIndex && heap[next] < heap[right]) next = right; // 오른쪽보다 작으면 오른쪽으로 보내기 (여기서는 위에 now랑 left랑 비교해서 더 큰애랑 또 비교해서 갱신하게됨)
            if (next == now) break;
            
            int temp = heap[now];
            heap[now] = heap[next];
            heap[next] = temp;
            
            now = next;
        }
        
        return ret;
    }
    
    public void Remove(int value)
    {
        heap.Remove(value);
    }
}

결과