[Algo Rhythm🕺💃]
난이도: Level 3
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
* 이때 숫자를 삽입하는 문자인 I는 대문자 I(아이) 를 의미한다.
16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.
PriorityQueue로 풀 수도 있지만.. 나는 sorting, remove, add등이 편리한 ArrayList로 풀었다.
ArrayList지만 편의상 이름을 queue로 두겠다.
ArrayList타입의 queue 변수 생성
operation 배열에 있는 값들을 for문으로 하나씩 search
1.1 한 행 기준으로 index가 0인 곳에는 문자, 1인 곳에는 숫자가 들어있기 때문에 split을 통해 구별한다.
1) 문자가 I인 경우
index가 1인 값을 int형으로 변환하여 queue에 넣는다.
2) 문자가 D인 경우
queue의 size가 0이면 연산할 값이 없기 때문에 continue를 해준다.
i) 숫자가 1인 경우
queue의 size-1에 있는 값을 삭제한다.
(정렬된 queue에서 제일 마지막 값이 최대값이기 때문에)
ii) 숫자가 -1인 경우 queue의 0에 있는 값을 삭제한다. (정렬된 queue에서 제일 처음 값이 최소값이기 때문에)
1.2 queue의 size가 0이 아닌 경우 queue를 오름차순으로 sorting한다.
queue의 size가 0인 경우 answer[0], answer[1]에 0을 대입
그렇지 않은 경우 queue의 최대값, 최소값 각각 대입
answer를 return한다.
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
int[] answer = new int[2];
ArrayList<Integer> opQueue = new ArrayList<>();
for(int i = 0; i < operations.length; i++){
String[] op = operations[i].split(" ");
if(op[0].trim().equals("I")){ // input the number
opQueue.add(Integer.parseInt(op[1]));
} else { // only D
if(opQueue.size() == 0) continue;
if(op[1].trim().equals("1")){ // output the max
opQueue.remove(opQueue.size()-1);
} else if(op[1].trim().equals("-1")){ // output the min
opQueue.remove(0);
}
}
if(opQueue.size() != 0) Collections.sort(opQueue);
}
if(opQueue.size() == 0){
answer[0] = 0;
answer[1] = 0;
}else{
answer[0] = opQueue.get(opQueue.size()-1);
answer[1] = opQueue.get(0);
}
return answer;
}
}