오늘의 문제는 프로그래머스 고득점 kit 힙 분류의 level3 문제이다 ! ( 문제 링크 )
힙 분류도 다 뽀갰다 ✅ 예이 ~ 토요일까지 고득점 kit 끝내고 싶은데 가능할런지 .. 적어도 이번주 내에는 끝날 것 같다 !
문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
| 명령어 | 수신 탑(높이) |
|---|---|
| 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] |
풀이 방법
처음엔 가장 큰 수와 가장 작은 수를 모두 알고있어야 하므로 pq 하나와 최대 혹은 최소값을 저장하는 변수로 안될까 ? remove가 있으니까 ? 라고 생각했으나 제거 후에 그 다음으로 작고 큰 수를 알아낼 방법이 없었다 !
따라서 제거한 후 그 다음 크고, 작은 수도 알 수 있어야 하므로 오름차순으로 정렬되는 pq 하나, 내림차순으로 정렬되는 pq 하나를 선언해두고 사용하였다.
또한 사이즈가 0인 경우에는 연산을 하지 않아야 하고, 최종적으로 사이즈가 0인 경우는 반환하는 값이 달라야 하는데 두 개의 큐를 사용하고 있으므로 count라는 실제 원소 개수를 저장하는 변수를 사용하였다.
operation 스트링을 " "를 delimiter로 split하고, 그 값들을 이용하여 연산의 종류를 알아내었다.
- 삽입 연산인 경우, min, max 우선 순위 큐에 모두 값을 넣어주고, 원소 개수도 증가시키다.
- 제거 연산인 경우,
- 원소 개수가 0이면 연산을 건너뛰어 주었고, 아니면 -연산이 붙었는지를 확인하였다.
- -가 붙은 경우 min에서 하나를 제거하고, 아닌 경우 max에서 하나를 제거한 후 원소 개수도 감소시켜 주었다.
처음에 결과 배열에 [0,0]을 넣어두었으므로, 최종적으로 원소 개수가 0이 아니라면 max와 min에서 각각 우선순위가 높은 원소 하나씩을 꺼내서 배열에 넣어서 반환한다.
❗️문제발생❗️
이 코드로 답안을 제출하였으나 첫 번째 테스트 케이스에서 문제가 발생하였다. 다양한 테스트 케이스를 고민하며 문제를 파악한 결과 문제는 다음과 같았다.
위의 코드에서는 두 개의 큐에 공통되게 존재하는 원소가 그 순서를 잡아주었다. 하지만 원소 제거를 해서 원소의 개수가 0이 되었다가 다시 원소를 삽입하는 경우, 실제로는 제거되었으나 남아있는 원소들이 순서를 망가뜨리게 되는 것이었다. ( 아래와 같은 경우 )
따라서 제거하는 연산이 발생하는 경우, 제거 후에 원소 개수가 0이 된다면 두 개의 큐를 clear해주는 코드를 추가해서 해결해주었다 !
코드
import java.util.Collections;
import java.util.PriorityQueue;
class Solution {
public int[] solution(String[] operations) {
int[] answer = {0, 0};
PriorityQueue<Integer> min = new PriorityQueue<>();
PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
String[] splited;
int count = 0;
for(String operation : operations){
splited = operation.split(" ");
switch (splited[0]){
case "I" : {
max.add(Integer.valueOf(splited[1]));
min.add(Integer.valueOf(splited[1]));
count ++;
break;
}
case "D" : {
if(count == 0) continue;
if(splited[1].charAt(0) == '-') min.poll();
else max.poll();
count--;
if(count == 0){
min.clear();
max.clear();
}
break;
}
}
}
if(count != 0){
answer[0] = max.poll();
answer[1] = min.poll();
}
return answer;
}
}