[프로그래머스] 이중우선순위 큐

문제

명령어	수신 탑(높이)
|숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

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

제한사항

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

풀이

1. Java : 자료를 정렬된 상태로 관리하며, 앞/뒤로 데이터 삭제가 가능한 자료구조인 TreeSet을 이용하면 쉽게 풀이할 수 있는 문제입니다.
2. Python : 새로운 숫자를 삽입할 때마다 오름차순 정렬

코드(Python)

def solution(operations):
    answer = []
    
    maps = []
    for op, num in [ x.split() for x in operations]:
        if op == 'I': # 삽입
            maps.append(int(num))
            maps.sort()
        elif maps:
            if num == '1': # 최댓값 삭제
                maps.pop(-1)
            else: # 최솟값 삭제
                maps.pop(0)
    return [maps[-1],maps[0]] if maps else [0,0]

코드(Java)

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        
        TreeSet<Integer> set = new TreeSet<>();
        
        for(int i = 0 ; i < operations.length ; i++){
            String[] operation = operations[i].split(" ");
            
            String opCode = operation[0];
            int num = Integer.parseInt(operation[1]);
            
            if(opCode.equals("I")){ //Insert
                set.add(num);
            }else{ //Delete
                if(num > 0){ //Max
                    set.pollLast();
                }else{ //Min
                    set.pollFirst();
                }
            }
        }
        
        if(set.isEmpty()) return new int[]{0,0};
        return new int[]{set.last(), set.first()};
    }
}