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

🔃 이중우선순위큐

 

Max Heap과 Min Heap을 이용하여 해결할 수 있다.

 

---

문제 설명

 

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

 

명령어
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]

 

---

🔑 IDEA

숫자를 오름차순으로 저장하는 minHeap과, 숫자를 내림차순으로 저장하는 maxHeap을 선언한다.

1. 삽입: minHeap과 maxHeap 모두에 숫자를 저장한다.
2. 최댓값 삭제: minHeap과 maxHeap에 공통으로 존재하는 max값을 maxHeap에서 찾아 삭제한다. 
3. 최솟값 삭제: minHeap과 maxHeap에 공통으로 존재하는 min값을 minHeap에서 찾아 삭제한다.

모든 명령을 수행한 뒤, minHeap과 maxHeap의 교집합에서 min값과 max값을 찾아 리턴한다. 

 

💡  나의 풀이

import java.util.*;

class Solution {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    
    public int[] solution(String[] operations) {
        for(String cmd: operations) {
            operate(cmd);
        }
        
        List<Integer> intersection = new ArrayList<>();
        for(int num: maxHeap) {
            if(minHeap.contains(num)) intersection.add(num);
        }
        if(intersection.isEmpty()) return new int[]{0,0};
        Collections.sort(intersection, Collections.reverseOrder());
        return new int[]{intersection.get(0), intersection.get(intersection.size()-1)};
    }
    
    private void operate(String cmd) {
        if(cmd.charAt(0) == 'I') {
            int num = Integer.parseInt(cmd.substring(2));
            minHeap.offer(num);
            maxHeap.offer(num);
        }
        else if(cmd.charAt(2) == '1') {
            while(!maxHeap.isEmpty() && !minHeap.contains(maxHeap.poll())) {

            }
        }
        else {
            while(!minHeap.isEmpty() && !maxHeap.contains(minHeap.poll())) {
                
            }
        }
    }
}

 

 

---

 

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