0. 문제
https://www.acmicpc.net/problem/7662문제를 간략하게 요약하자면
기능 값 모양으로 입력받으며 기능에 따라 값을 넣을지 뺄지를 선택하는 것이다.
D 1 : 큐의 최댓값 삭제
D -1 : 큐의 최소값 삭제
I n : n이란값을 넣기
최종적으로 최댓값 최소값 형태를 출력하는 것이고 만약 큐가 비어있다면 empty 를 출력한다.
1. 내 풀이
import java.util.*;
import java.io.*;
public class Main{
public static void Que(String[] input,PriorityQueue<Integer> upperqueue,PriorityQueue<Integer> lowerqueue){
// 우선순위큐를 2개 써서 하나는 오름차순 하나는 내림차순 으로 사용함
String order = input[0];
int num = Integer.parseInt(input[1]);
if(Objects.equals(order, "D")){
if(num==-1){
Integer a = upperqueue.poll(); // 최소값
if(a!=null){
lowerqueue.remove(a);
}
}
else{
Integer a = lowerqueue.poll(); // 최댓값
if(a!=null){
upperqueue.remove(a);
}
}
}
else{
upperqueue.add(num);
lowerqueue.add(num);
}
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(bf.readLine());
for(int i=0;i<tc;i++){
PriorityQueue<Integer> upperqueue = new PriorityQueue<>();
PriorityQueue<Integer> lowerqueue = new PriorityQueue<>(Collections.reverseOrder());
int ordercount = Integer.parseInt(bf.readLine());
for(int j=0;j<ordercount;j++){
String[] input = bf.readLine().split(" ");
Que(input,upperqueue,lowerqueue);
}
StringBuilder sb = new StringBuilder();
if(upperqueue.isEmpty() && lowerqueue.isEmpty()){
sb.append("EMPTY");
}
else{
sb.append(lowerqueue.peek()).append(" ").append(upperqueue.peek());
}
System.out.println(sb);
}
}
}나는 우선 순위 큐를 사용하였다.
PriorityQueue<Integer> upperqueue = new PriorityQueue<>();
PriorityQueue<Integer> lowerqueue = new PriorityQueue<>(Collections.reverseOrder());PriorityQueue는 기본적으로 어떤 값이 들어와도 오름차순 형태로 정렬해주는 Queue 자료구조다.
PriorityQueue 뒤에 Collections.reverseOrder()) 를 사용하면 역순으로 정렬해준다.
PriorityQueue의 peek() , poll() 을 사용하여 각 큐에서 최솟값, 최댓값을 추출할 생각이다.
public static void Que(String[] input,PriorityQueue<Integer> upperqueue,PriorityQueue<Integer> lowerqueue){
// 우선순위큐를 2개 써서 하나는 오름차순 하나는 내림차순 으로 사용함
String order = input[0];
int num = Integer.parseInt(input[1]);
if(Objects.equals(order, "D")){
if(num==-1){
Integer a = upperqueue.poll(); // 최소값
if(a!=null){
lowerqueue.remove(a);
}
}
else{
Integer a = lowerqueue.poll(); // 최댓값
if(a!=null){
upperqueue.remove(a);
}
}
}
else{
upperqueue.add(num);
lowerqueue.add(num);
}
}poll() 과 peek()은 큐가 비었을 경우 null을 반환시킨다.
따라서 추출한 값이 null이 아닌 경우(실제로 추출했을때)만 다른 큐도 똑같이 해당 값을 삭제해줘서 두개의 큐를 동기화 시켜줬다.
로직만으로는 정상 작동하였지만 시간초과가 발생하였다.
2. 문제점
시간초과의 원인은 Queue.remove(num) 에서 발생하였다.
Queue.remove(num) 은 내부를 선형 탐색하여 값을 찾는것으로 한쪽에서 값을 삭제(추출) 시키면 다른쪽에서 해당 값을 찾는데 처음부터 끝까지 순회해서 찾아야 한다.
따라서 개수가 많아질수록 당연히 선형 탐색하는 시간이 길어져 시간초과가 날 수 밖에 없다.
3. 해결법
3-1. Lazy detection + clean()
이번에 처음 듣는 기법이였다.
- Lazy detection
Lazy detection은 두개의 큐를 동기화할때 한쪽만 처리하고 나머지 큐는 Map을 통해 검증하여 쓰레기값일 경우 그냥 없애버리는 방식이다.
해당 기법의 가장 핵심은Map<Integer,Integer> cnt를 통한 유효 카운팅을 이용해 유효 값만 남기고 나머지는 버려버리는 기법이다.
upperqueue.add(x);
lowerqueue.add(x);
if (map.containsKey(x)) {
map.put(x, map.get(x) + 1);
} else {
map.put(x, 1);
}x라는 값을 두 큐에 넣었을 경우 map 자료구조에 해당 값이 몇개 있는지 넣어준다.
static void clean(PriorityQueue<Integer> pq, Map<Integer,Integer> cnt) {
while (!pq.isEmpty()) {
int x = pq.peek();
Integer c = cnt.get(x);
if (c == null || c == 0) pq.poll(); // 구식 값 버리기
else break; // 유효한 값이면 멈춤
}
}여기가 가장 중요한 곳이다.
큐의 head값을 검사하여 map에 더이상 없는(카운팅이 되지 않는)값일경우 전부 버려버린다.
언제까지 > 큐가 전부 비거나 유효값(아직 살아있는값)이 나올때까지 버린다.
위 방식을 이용하면 결론적으로 선형 큐를 딱 한번만 탐색하는 모습이 그려진다.
clean() 함수가 동작하는 작은 예시로
I 3
I 3
I 2
D 1라는 테스트케이스가 있다고 가정하자.
- case1 (I 3)
minPQ = [3]
maxPQ = [3]
cnt = {3:1}- case2 (I 3)
minPQ = [3,3]
maxPQ = [3,3]
cnt = {3:2}- case3 (I 2)
minPQ = [2,3,3] // 오름차순 우선순위큐
maxPQ = [3,3,2] // 내림차순 우선순위큐
cnt = {3:2 , 2:1}- case4 (D 1) 최댓값 삭제
clean(maxPQ,cnt)
maxPQ.peek() = 3 // cnt[3] = 2니까 유효한 상태임
maxPQ.poll() // cnt[3] = 1 꺼냇으니까 1 줄어듬
clean(minPQ,cnt)
minPQ.peek() = 2 // cnt[2] = 1니까 유효한 상태임 건드리기x결론적으로 최종 코드는
import java.util.*;
import java.io.*;
public class Main {
// pq의 꼭대기에 이미 반대쪽에서 소진되어 유효하지 않은 값(= cnt[x]==0)이 올라와 있으면
// 그 값을 버리면서( poll ) 유효한 값이 나올 때까지 정리해주는 함수
static void clean(PriorityQueue<Integer> pq, Map<Integer, Integer> cnt) {
while (!pq.isEmpty()) {
int x = pq.peek();
Integer c = cnt.get(x);
if (c == null || c == 0) {
pq.poll(); // 구식(stale) 값 제거
} else {
break; // 유효한 값이면 중단
}
}
}
public static void Que(String[] input,
PriorityQueue<Integer> minPQ,
PriorityQueue<Integer> maxPQ,
Map<Integer,Integer> cnt) {
String order = input[0];
int num = Integer.parseInt(input[1]);
if (order.equals("I")) {
// 삽입: 두 힙에 모두 넣고 유효 개수 +1
minPQ.offer(num);
maxPQ.offer(num);
cnt.put(num, cnt.getOrDefault(num, 0) + 1);
} else { // "D"
if (num == 1) { // 최댓값 삭제
clean(maxPQ, cnt);
if (!maxPQ.isEmpty()) {
int top = maxPQ.poll();
int c = cnt.get(top) - 1;
if (c == 0) cnt.remove(top);
else cnt.put(top, c);
}
} else { // num == -1, 최솟값 삭제
clean(minPQ, cnt);
if (!minPQ.isEmpty()) {
int top = minPQ.poll();
int c = cnt.get(top) - 1;
if (c == 0) cnt.remove(top);
else cnt.put(top, c);
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringBuilder out = new StringBuilder();
int tc = Integer.parseInt(bf.readLine());
for (int i = 0; i < tc; i++) {
int ordercount = Integer.parseInt(bf.readLine());
PriorityQueue<Integer> minPQ = new PriorityQueue<>(); // 최소힙
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder()); // 최대힙
Map<Integer,Integer> cnt = new HashMap<>(); // 유효 개수 카운트
for (int j = 0; j < ordercount; j++) { // ← j 사용 주의!
String[] input = bf.readLine().split(" ");
Que(input, minPQ, maxPQ, cnt);
}
// 출력 전 최종 정리
clean(minPQ, cnt);
clean(maxPQ, cnt);
if (cnt.isEmpty()) {
out.append("EMPTY\n");
} else {
out.append(maxPQ.peek()).append(' ').append(minPQ.peek()).append('\n');
}
}
System.out.print(out.toString());
}
}3-2. Treemap
PQ는 head만 처리하고 tail은 처리하지 않아 Lazy Detection 기법을 사용해서 풀어야만 했다.
하지만, 중복을 허용하면서 정렬 기반 자료구조며 tail도 처리 가능한 자료구조인 Treemap을 사용하는 방법이 오히려 이 문제에 더 적합한 자료구조다.
- 전체 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder out = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int tc = 0; tc < T; tc++) {
int k = Integer.parseInt(br.readLine());
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < k; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String op = st.nextToken();
int x = Integer.parseInt(st.nextToken());
if (op.equals("I")) {
map.put(x, map.getOrDefault(x, 0) + 1);
} else { // "D"
if (map.isEmpty()) continue; // 비었으면 무시
if (x == 1) { // 최댓값 삭제
Map.Entry<Integer,Integer> e = map.lastEntry();
int cnt = e.getValue() - 1;
if (cnt == 0) map.pollLastEntry(); else map.put(e.getKey(), cnt);
} else { // 최솟값 삭제
Map.Entry<Integer,Integer> e = map.firstEntry();
int cnt = e.getValue() - 1;
if (cnt == 0) map.pollFirstEntry(); else map.put(e.getKey(), cnt);
}
}
}
if (map.isEmpty()) out.append("EMPTY\n");
else out.append(map.lastKey()).append(' ').append(map.firstKey()).append('\n');
}
System.out.print(out.toString());
}
}위 코드를 살펴보면
if (map.isEmpty()) continue;우선 삭제 명령인 D가 들어갔는데 맵이 비어있으면 아무것도 하지 않고 넘겨준다.
if (x == 1) { // 최댓값 삭제
Map.Entry<Integer,Integer> e = map.lastEntry();
int cnt = e.getValue() - 1;
if (cnt == 0) map.pollLastEntry(); else map.put(e.getKey(), cnt);
} else { // 최솟값 삭제
Map.Entry<Integer,Integer> e = map.firstEntry();
int cnt = e.getValue() - 1;
if (cnt == 0) map.pollFirstEntry(); else map.put(e.getKey(), cnt);
}
최댓값 삭제일 경우 오름차순 정렬이므로 가장 뒤에 있는 값의 Entry를 가져온다.
여기서 Entry는 (key,value)쌍을 담는 객체다.
최댓값을 추출했으므로 해당 값의 카운팅(cnt)를 하나 줄여준 뒤에 값을 검사한다.
cnt가 0이면 더이상 필요없는 값이므로 map에서 없애준다 pollLastEntry
cnt가 0이 아니면 값만 갱신해준다. map.put
if (map.isEmpty()) out.append("EMPTY\n");
else out.append(map.lastKey()).append(' ').append(map.firstKey()).append('\n');결론적으로 정렬된 map을 통해 최대,최소 혹은 비어있는지 유무까지 검사하여 최종 답안을 도출할 수 있다.
프론트엔드 개발자 지망생입니다