문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0]
비어있지 않으면 [최댓값, 최솟값]
을 return 하도록 solution 함수를 구현해주세요.
제한사항
operations
는 길이가 1 이상 1,000,000 이하
인 문자열 배열입니다.operations
의 원소는 큐가 수행할 연산을 나타냅니다.“명령어 데이터”
형식으로 주어집니다. 최댓값/최솟값
을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제
합니다.빈 큐
에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시
합니다.입출력 예
나의 풀이
문제 유형은 우선순위큐를 이용하여 푸는 문제였지만, 처음 내 생각으로는 우선순위 큐로 구현하면, 최솟값과 최댓값을 번갈아가며 접근하기에 힘이 들것같아서 ArrayList로 문제를 풀었다.
삭제 명령이 있을 때마다 ArrayList를 정렬하여, 삭제 해주었다.
import java.util.*;
import java.lang.*;
class Solution {
ArrayList<Integer> list = new ArrayList<>();
public int[] solution(String[] operations) {
int[] answer = {};
for(int i=0;i<operations.length;i++){
String [] str = operations[i].split(" ");
//System.out.printf("%s %s\n", str[0], str[1]);
if(str[0].equals("I")){
int temp = Integer.parseInt(str[1]);
list.add(temp);
System.out.println(temp);
}
else if(str[0].equals("D")){
if(list.size()==0){
continue;
}
else{
int temp = Integer.parseInt(str[1]);
if(temp==-1){
Collections.sort(list);
list.remove(0);
}
else{
Collections.sort(list);
list.remove(list.size()-1);
}
}
}
}
Collections.sort(list);
answer = new int[2];
if(list.size()==0){
answer[0]=0;
answer[1]=0;
}
else{
answer[0] = list.get(list.size()-1);
answer[1] = list.get(0);
}
return answer;
}
}
우선순위 큐를 이용한 풀이법(자료를 검색하였음)
import java.util.*;
class Solution {
public static int[] solution(String[] operations) {
int[] answer = new int[2];
//최소 힙, 최대 힙
PriorityQueue<Integer> pq = new PriorityQueue<>();
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
for (String op : operations) {
StringTokenizer st = new StringTokenizer(op);
String judge = st.nextToken();
int value = Integer.parseInt(st.nextToken());
//빈 큐에 데이터를 삭제 요청 경우 연산 무시
if (pq.size() < 1 && judge.equals("D"))
continue;
//삽입 시 최소 힙, 최대 힙에 value 넣기
if (judge.equals("I")) {
pq.offer(value);
maxPq.offer(value);
continue;
}
//나머지 경우는 D이면서 value값이 1인지 -1인지 이므로
//0보다 작은 경우 최소 힙에서 poll후 최대힙에서 해당 원소 삭제
if(value < 0) {
int min = pq.poll();
maxPq.remove(min);
continue;
}
//최대 힙에서 poll후 최소힙에서 해당 원소 삭제
int max = maxPq.poll();
pq.remove(max);
}
if(pq.size() > 0 ) {
answer[0] = maxPq.poll();
answer[1] = pq.poll();
}
return answer;
}
}