핵심 :
reverse를 안 쓰면 굉장히 속도가 느립니다! (풀리긴 합니다.)
List만 갖고 풀어도 풀리긴 합니다 ← 근데 이름 자체가 이중우선순위큐라... ㅎ
굳이 PriorityQueue를 안 쓰고 max랑 min 을 쓰면 풀리긴 하나 속도가 느립니다!
시간 복잡도 관련 문제가 아니라 풀리는 게 맞긴 한데 속도가 문제임!
package programmers;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
public class 이중우선순위큐_221230 {
public static void main(String[] args) {
//String [] operations = {"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"};
String [] operations = {"I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"};
int [] arr = solution(operations);
System.out.println(Arrays.toString(arr));
}
public static int[] solution(String[] operations) {
/*
16과 -5643을 삽입합니다.
최솟값을 삭제합니다. -5643이 삭제되고 16이 남아있습니다.
최댓값을 삭제합니다. 16이 삭제되고 이중 우선순위 큐는 비어있습니다.
우선순위 큐가 비어있으므로 최댓값 삭제 연산이 무시됩니다.
123을 삽입합니다.
최솟값을 삭제합니다. 123이 삭제되고 이중 우선순위 큐는 비어있습니다.
I 숫자 큐에 주어진 숫자를 삽입합니다.
D 1 큐에서 최댓값을 삭제합니다.
D -1 큐에서 최솟값을 삭제합니다.
*
*/
int [] answer = new int[2];
PriorityQueue <Integer> minQueue = new PriorityQueue <Integer>();
PriorityQueue <Integer> maxQueue = new PriorityQueue <Integer>(Collections.reverseOrder()); //reverse를 매번 시키지 말고 이걸 쓰자!
String [] temp = new String[2];
for(String s : operations){
temp = s.split(" ");
//System.out.println("ㅎㅅㅎ" + temp[0] + " " + temp[1]);
switch(temp[0]){
case "I":
//큐에 숫자 삽입
minQueue.add(Integer.parseInt(temp[1]));
maxQueue.add(Integer.parseInt(temp[1]));
break;
case "D":
if(minQueue.isEmpty()){
break;
}else if(temp[1].equals("-1")){
//최소값 삭제
maxQueue.remove(minQueue.poll());
break;
}else{
//최대값 삭제
minQueue.remove(maxQueue.poll());
break;
}
default:
break;
}
}
/*
while(!minQueue.isEmpty()){
System.out.println("ㅇㅅㅇ" + minQueue.poll());
}
*/
if(minQueue.isEmpty()){
answer[0] = 0;
answer[1] = 0;
}else{
answer[0] = maxQueue.peek();
answer[1] = minQueue.peek();
}
return answer;
}
}
이거 테스트 용으로 짜둔 poll 때문에 잠시 고민함... (왜 비워지지...)
왜 무조건 null 이지의 이유 : 테스트 코드를 넣었단다! 인 경우입니다.
while(!minQueue.isEmpty()){
System.out.println(minQueue.poll());
}
아무튼 재미있는 문제였음.
댓글
댓글 쓰기