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

힙을 활용하는 Lv3문제입니다.

---

문제 설명

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

명령어수신 탑(높이)

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]

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

---

<내 풀이>

특정 형태의 문자열을 담은 배열이 입력값으로 주어진다.

문자열을 한개씩 받아서 split을 활용해 공백기준으로 나누고 앞쪽 문자가 I인지 D인지를 기준으로 우선 구분하고

I이면 공백 뒤 문자를 큐에 삽입, D이면 공백뒤 문자가 -1인지 1인지 확인 후 해당 작업을 한다.

최종적으로 반환해야하는 값이 최대, 최소값인데 큐를 한개만 활용할 경우 큐의 특성상 한가지 값만 반환이 가능하다.

따라서 각각 내림차순과 오름차순 두가지로 정렬되어 동작하는 우선순위큐를 만들고

두 큐에 입력값에 대한 작업을 동시에 해주고

최종적으로 각각의 큐에서 최대값과 최솟값을 반환받을 수 있다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue <Integer> q = new PriorityQueue<>();
        PriorityQueue <Integer> reverse_q = new PriorityQueue<>(Collections.reverseOrder());
        for(String operation : operations){
            String[] splitValue = operation.split(" ");
            
            if(splitValue[0].equals("I")){
                q.add(Integer.parseInt(splitValue[1]));
                reverse_q.add(Integer.parseInt(splitValue[1]));
            }
            
            if(splitValue[0].equals("D")){
                if(splitValue[1].equals("-1") && !q.isEmpty()){
                    int min = q.poll();
                    reverse_q.remove(min);
                }
                if(splitValue[1].equals("1") && !reverse_q.isEmpty()){
                    int max = reverse_q.poll();
                    q.remove(max);
                }
            }
        }
        int[] answer = {0, 0};
        if (!q.isEmpty()) {
            answer[0] = reverse_q.peek();
            answer[1] = q.peek();
        }
        return answer;
    }
}

어렵지 않게 풀었다 ㅇㅅㅇ 이전 2레벨 힙문제가 더 어려웠던것 같다ㅜ

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐 | 프로그래머스