https://www.acmicpc.net/problem/7662
문제 요약
이중 우선순위 큐 Q는 우선순위 큐와 유사하지만, 두 가지 데이터 삭제 연산을 지원한다.
즉, 우선순위가 가장 낮은 것을 삭제하거나 가장 높은 것을 삭제할 수 있다.
연산은 다음과 같이 주어진다.
- I n: Q에 정수 n를 삽입한다.
- D 1: Q의 최댓값을 삭제한다.
- D -1: Q의 최솟값을 삭제한다.
삭제 연산에서 최대 또는 최소가 둘 이상이라면 그 중 하나만 삭제된다.
또한, Q가 비어있다면 삭제 연산은 무시된다.
이러한 작업은 테스트 케이스 T번 주어진다.
각 케이스에서 연산의 개수 k는 최대 100만이다.
삽입되는 정수 n은 Integer가 지원하는 범위 내에 존재한다.
입력받는 정수를 우선순위로 사용하여 이중 우선순위 큐 Q에 연산을 수행하고, 최종적으로 Q에 남은 데이터 중 최댓값과 최솟값을 찾아라.
만약 Q가 비어있다면 "EMPTY"를 출력한다.
문제 접근
각 케이스에서 연산이 최대 100만 번 주어지기 때문에, 이를 처리하는 작업이 O(NlogN)내에 처리되어야 전체 테스트 케이스를 시간 내에 처리할 수 있다.
이때 각 연산을 훑는 O(N)은 반드시 필요하기 때문에, 각 연산 처리를 O(logN)에 해야한다는 것을 알 수 있다.
최대 우선순위 큐와 최소 우선순위 큐 두 가지를 사용하면 문제를 해결할 수 있을 것 같다.
문제는 다른쪽 큐에서 삭제된 값을 현재 큐에서 인식할 수 있어야 한다는 것이다.
단순히 숫자를 기록하면 된다고 생각할 수 있지만, 동일한 숫자가 여러 번 삽입되고 삭제될 수 있기 때문에 간단하지 않다.
나의 아이디어는 연산 번호를 큐에 같이 넣어주는 것이다.
여기서 연산 번호란, 각 테스트 케이스에서 해당 값이 삽입된 연산의 순서를 의미한다.
값을 삽입할 때, {숫자, 연산 번호}의 형태를 사용하고, 값을 삭제할 때는 해당 연산 번호를 기록하면 된다.
그러면 다른 우선순위 큐에서 또 값을 삭제해야 할 때 해당 숫자가 삭제되었는지를 확인해서 처리할 수 있다.
삭제 연산 번호 기록에 HashSet을 사용하면 삽입 및 확인이 O(1)에 처리되니까 충분히 처리할 수 있을 것 같다.
고민점 1. 삭제 여부를 판단하는 시간복잡도가 어떻게 될까?
한 가지 걱정이 되는 것은 값을 삭제할 때마다 삭제 여부를 확인하는 것이 시간 초과로 이어질 수도 있지 않을까? 라는 점이다.
하지만 이는 걱정할 필요가 없다.
왜냐하면 삭제 여부를 한 번 확인해서 쓰레기값을 삭제한 이후로는 해당 값을 다시 확인할 필요 없기 때문이다. 그리고 한 연산에서 삭제 여부를 여러 번 확인하는 경우는 값을 삽입하고 삭제한 뒤 다른 큐에서 또 삭제를 할 때인데, 최대 연산이 100만 개이므로 삽입 후 삭제는 최대 50만 번 나타날 수 있다.
죽, 각 테스트 케이스 전체에서 에 수행될 수 있으므로 문제가 되지 않는다.
고민점 2. 같은 숫자가 들어오는 경우가 잘 처리될까?
또 고민할 수 있는 점은, 연산 번호로 판단하면 같은 값을 잘 처리할 수 있는 지의 여부이다.
그런데 이것도 문제가 안 된다.
왜냐하면 같은 값에서 삭제된 값과 삭제되지 않은 값이 혼재되어 있어도 삭제되지 않은 값이 있다면 해당 값이 최대/최소의 역할을 수행할 수 있으며, 모두 삭제되었다면 삭제 여부 판단을 통해 다음 값으로 넘어가지기 때문이다.
풀이
기본적인 아이디어는 다음과 같다.
- 각 테스트 케이스에 대해 우선순위가 반대인 우선순위 큐 두 개를 생성하고, 삭제 여부를 기록할 셋을 하나 생성한다.
- 삽입은 {숫자, 연산 번호}로 두 큐에 모두 수행한다.
- 삭제는 해당 큐에서 수행하는데, 연산 번호를 셋에서 확인해 이미 삭제된 값이라면 다음 값으로 넘어간다. 삭제 수행 후에는 해당 숫자의 연산 번호를 셋에 기록한다.
- 연산을 모두 처리한 후에 최댓값, 최솟값을 얻을 때에도 연산 번호로 삭제 여부를 확인하며 가져온다.
여기서 중요하고 조금 골치아픈 점은, 삭제 여부를 확인해서 다음 값으로 넘어갈 때마다 항상 해당 큐가 비어있지는 않은지 확인해야 한다는 점이다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder answer = new StringBuilder();
// 테스트 케이스 입력 받기
int T = Integer.parseInt(br.readLine());
// 각 테스트 케이스에 대해 수행
for (int tc = 0; tc < T; tc++) {
// 필요한 자료구조 선언
// 낮은 값이 우선순위를 갖는 큐, {숫자, 연산 순서}로 저장
PriorityQueue<int[]> smallFirstQ = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] a1, int[] a2) {
return Integer.compare(a1[0], a2[0]);
}
});
// 높은 값이 우선순위를 갖는 큐, {숫자, 연산 순서}로 저장
PriorityQueue<int[]> bigFirstQ = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] a1, int[] a2) {
return Integer.compare(a2[0], a1[0]);
}
});
// 삭제한 숫자의 연산 번호를 기록하는 셋
HashSet<Integer> removed = new HashSet<>();
// 연산 개수 입력 받기
int numOp = Integer.parseInt(br.readLine());
// 각 연산을 수행
for (int now = 0; now < numOp; now++) {
// 연산 입력 받기
StringTokenizer stOp = new StringTokenizer(br.readLine());
char op = stOp.nextToken().charAt(0);
int num = Integer.parseInt(stOp.nextToken());
// 삽입 연산인 경우
if (op == 'I') {
// {숫자, 연산 번호} 구성
int[] numPair = {num, now};
// 두 큐에 삽입
smallFirstQ.add(numPair);
bigFirstQ.add(numPair);
}
// 삭제 연산인 경우
else if (op == 'D') {
// 두 큐 중 하나라도 비어있다면 넘어감
if (bigFirstQ.isEmpty() || smallFirstQ.isEmpty()) continue;
// 최댓값 삭제인 경우
if (num == 1) {
// 최대 우선 큐에서 값을 꺼냄
int[] numPair = bigFirstQ.poll();
// 보유하고 있다면 다시 꺼내도록 함
while (removed.contains(numPair[1])) {
// 큐가 비어있다면 넘어감
if (bigFirstQ.isEmpty()) break;
numPair = bigFirstQ.poll();
}
// 보유하지 않은 값이 확인되면 현재 연산 번호를 기록
removed.add(numPair[1]);
}
// 최솟값 삭제인 경우
else if (num == -1){
// 최소 우선 큐에서 값을 꺼냄
int[] numPair = smallFirstQ.poll();
// 보유하고 있다면 다시 꺼내도록 함
while (removed.contains(numPair[1])) {
// 큐가 비어있다면 넘어감
if (smallFirstQ.isEmpty()) break;
numPair = smallFirstQ.poll();
}
// 보유하지 않은 값이 확인되면 현재 연산 번호를 기록
removed.add(numPair[1]);
}
}
}
// 연산 수행 종료 후 최댓값, 최솟값 기록
// 비어있다면 EMPTY 출력
if (bigFirstQ.isEmpty() || smallFirstQ.isEmpty()) {
answer.append("EMPTY\n");
}
else {
int[] smallNumPair = smallFirstQ.poll();
int[] bigNumPair = bigFirstQ.poll();
boolean isEmpty = false;
while (removed.contains(smallNumPair[1])) {
// 큐가 비어있다면 기록
if (smallFirstQ.isEmpty()) {
isEmpty = true;
break;
}
smallNumPair = smallFirstQ.poll();
}
while (removed.contains(bigNumPair[1])) {
// 큐가 비어있다면 기록
if (bigFirstQ.isEmpty()) {
isEmpty = true;
break;
}
bigNumPair = bigFirstQ.poll();
}
// 큐가 비어있다면 EMPTY 출력
if (isEmpty) {
answer.append("EMPTY\n");
}
// 아니라면 최댓값, 최솟값 출력
else {
answer.append(bigNumPair[0]);
answer.append(" ");
answer.append(smallNumPair[0]);
answer.append("\n");
}
}
}
// 모든 테스트 케이스 처리 후 결과 출력
System.out.println(answer);
}
}회고
사실 온전히 내 생각으로 푼 문제는 아니고, 다른 쪽 우선순위 큐에서 삭제된 것을 어떻게 처리하는지 대충 찾아보다가 기록을 하면 된다는 정보를 기반으로 해결했다.
그래도 연산 순서를 사용하는 풀이는 본 적이 없는 것 같다? 일반적으로는 각 숫자의 개수를 기반으로 PriorityQueue와 HashMap을 동시에 사용하거나, 아니면 TreeMap을 사용하는 방식 두 가지가 대표적인 것 같다. 풀이를 보면 확실히 TreeMap 하나를 사용하는 방식이 굉장히 간단하다.
나는 일단 TreeMap은 사용해본 적이 없어서 몰랐고, 문제를 직관적으로 해결하려고 했는데, 그러다보니 우선순위 큐가 비어있는지 확인하는 과정이 좀 복잡하게 수행되기는 했다. TreeMap은 최대 최소를 모두 알 수 있다는 것을 보니 유용하게 사용할 수 있을 것 같다.
