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

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

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

import java.util.Collections;
import java.util.PriorityQueue;
class Solution {
	    public int[] solution(String[] operations) {
	        int[] answer = new int[2];
	        
	        PriorityQueue<Integer> minHeap=new PriorityQueue<>();
	        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(Collections.reverseOrder());
	        
	        for(int i=0; i<operations.length; i++) {
	        	String operation[]=operations[i].split(" ");
	        	
	        	if(operation[0].equals("I")) { //삽입
	        		minHeap.add(Integer.parseInt(operation[1]));
	        		maxHeap.add(Integer.parseInt(operation[1]));
	        	}
	        	else { //삭제
	        		if(operation[1].equals("-1"))  minHeap.poll();//최솟값 삭제
	        		else maxHeap.poll(); //최댓값 삭제
	        		
	        		if(minHeap.size()==0 || maxHeap.size()==0 ||
	        				(minHeap.size()==1 && maxHeap.size()==1)) { //둘 중 하나라도 비었으면 다비워줌
	        			minHeap.clear();
	        			maxHeap.clear();
	        		}
	        	}
	        }
	        
	        if(maxHeap.size()==0) answer[0]=answer[1]=0; //큐 비어있으면
	        else {
	        	answer[0]=maxHeap.poll();
	        	answer[1]=minHeap.poll();
	        }
	        return answer;
	    }
	}

소요시간 : 16분

 

최댓값, 최솟값을 관리하기 위해 우선순위큐를 2개 사용하였습니다.

 

우선 I가 들어오면

최댓값 큐, 최솟값 큐 둘다 삽입을 해줍니다.

 

만약 D 1(최댓값 삭제)이 들어왔다면 최댓값 큐에서 poll해줍니다.

만약 D -1(최솟값 삭제)이 들어왔다면 최솟값 큐에서 poll해줍니다.

 

큐가 비는 경우는 2가지 있습니다.

 

1.하나의 입력을 받은 뒤 바로 삭제를 하는경우 -> 두개의 큐중 하나라도 크기가 0이면  두개의 큐 모두 초기화를 해줍니다.

 

2. 2개의 값이 남아있을 때 최솟값 한번삭제, 최댓값 한번삭제, -> 큐 두개가 모두 크기가 1이면 두개의 큐 모두 초기화

 

 

끝~