문제
이 문제는 대놓고 우선순위큐를 2개 사용하라고 제시한 문제이다.
정렬된 Deque 자료구조 를 구현하는 문제라고 생각했다.
초반 문제 접근
첫번째 접근
우선순위 큐를 두개 두고, 두 곳에 다 집어 넣는다.
최댓값을 구할 때는 DESC에서 뽑고, 최솟값을 구할 때는 ASC에서 뽑자.
이 접근법은 한 큐에서만 사라져서 다른 큐에서 찾아 없애는 것을 고민하다 관두었다.
두번째 접근
두 개를 두고, 어떤 값을 기준으로 하여금 어떤 큐에 넣을지 결정하여 넣는다.
이 접근에서 막힌 곳은 한곳으로 쏠렸을 때 어떻게 해야 할지가 관건이었다.
다시 빼서 넣는 순간 반복문이 내부에서 돌아야 하기 때문에 시간초과가 날 것이라고 생각했다.
일단은 진행하기로 함. 그렇게 만난 첫번째 오답.
첫번째 오답: 피벗을 두고 내림차순 + 오름차순 우선순위 큐 두개 구현
인풋 범위값이 Integer 범위이기 때문에 일단 단순히 0을 기준으로 두었다.
구현하면서도 애매한 부분이 많았다.
- 둘 중 하나의 큐가 비어있을 때 처리가 애매함. 반복문이 내부에서 발생할 수 밖에 없다.
- 꺼내는 과정도 복잡하다고 생각했음.
코드
package solution;
import java.util.*;
import java.io.*;
public class BOJ7662_이중우선순위큐 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder ans = new StringBuilder();
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
PriorityQueue<Integer> pqOrderByASC = new PriorityQueue<>();
PriorityQueue<Integer> pqOrderByDESC = new PriorityQueue<>(Comparator.reverseOrder());
int PIVOT = 0;
int k = Integer.parseInt(br.readLine());
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
char op = st.nextToken().charAt(0);
int n = Integer.parseInt(st.nextToken());
if (op == 'I') {
if (n > PIVOT) pqOrderByDESC.offer(n);
else pqOrderByASC.offer(n);
} else {
if(pqOrderByDESC.isEmpty() && pqOrderByASC.isEmpty()) continue;
if(n == 1) {
if(pqOrderByDESC.isEmpty()) {
while(!pqOrderByASC.isEmpty()) pqOrderByDESC.offer(pqOrderByASC.poll());
}
pqOrderByDESC.poll();
} else {
if(pqOrderByASC.isEmpty()) {
while(!pqOrderByDESC.isEmpty()) pqOrderByASC.offer(pqOrderByDESC.poll());
}
pqOrderByASC.poll();
}
}
}
String res;
if(pqOrderByDESC.isEmpty() && pqOrderByASC.isEmpty()) {
res = "EMPTY";
} else if (pqOrderByDESC.isEmpty()) {
int min = pqOrderByASC.peek();
while(pqOrderByASC.size() > 1) pqOrderByASC.poll();
int max = pqOrderByASC.poll();
res = max + " " + min;
} else if (pqOrderByASC.isEmpty()) {
int max = pqOrderByDESC.peek();
while(pqOrderByDESC.size() > 1) pqOrderByDESC.poll();
int min = pqOrderByDESC.poll();
res = max + " " + min;
} else {
res = pqOrderByDESC.poll() + " " + pqOrderByASC.poll();
}
ans.append(res).append("\n");
}
System.out.println(ans);
}
}결과
12%에서 틀렸습니다 뜬다.
두번째 시도: 성공
첫번째 접근을 진행하면서 내가 한 큐에서 제외한 원소를 다른 큐에서도 알 수 있게 Map을 활용해 원소를 표시해볼 수 있겠다고 생각했다.
코드
package solution;
import java.util.*;
import java.io.*;
public class BOJ7662_이중우선순위큐 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder ans = new StringBuilder();
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
PriorityQueue<Integer> pqOrderByASC = new PriorityQueue<>();
PriorityQueue<Integer> pqOrderByDESC = new PriorityQueue<>(Comparator.reverseOrder());
Map<Integer, Integer> dict = new HashMap<>(); // 키:큐의 들어간 원소값 값:몇 개 들어가있냐
int k = Integer.parseInt(br.readLine());
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
char op = st.nextToken().charAt(0);
int n = Integer.parseInt(st.nextToken());
if (op == 'I') {
// 두 큐에 n을 둘 다 넣고, dict 갱신한다.
pqOrderByDESC.offer(n);
pqOrderByASC.offer(n);
if(dict.containsKey(n)) dict.put(n, dict.get(n) + 1);
else dict.put(n, 1);
} else {
if(pqOrderByDESC.isEmpty() && pqOrderByASC.isEmpty()) continue;
if(n == 1) {
// 최댓값 삭제
// 유효한 값인지 체크
while(!pqOrderByDESC.isEmpty()) {
int tmp = dict.get(pqOrderByDESC.peek());
if(tmp > 0) break;
else pqOrderByDESC.poll();
}
// pq가 empty인지 체크
if(pqOrderByDESC.isEmpty()) continue;
// 최댓값 삭제
int deleteNum = pqOrderByDESC.poll();
// dict 갱신
dict.replace(deleteNum, dict.get(deleteNum) - 1);
} else {
// 최솟값 삭제
// 유효한 값인지 체크
while(!pqOrderByASC.isEmpty()) {
int tmp = dict.get(pqOrderByASC.peek());
if(tmp > 0) break;
else pqOrderByASC.poll();
}
// pq가 empty인지 체크
if(pqOrderByASC.isEmpty()) continue;
// 최솟값 삭제
int deleteNum = pqOrderByASC.poll();
// dict 갱신
dict.replace(deleteNum, dict.get(deleteNum) - 1);
}
}
}
// 값을 위해서 max, min을 큐를 순회하면서 갱신했다.
long max = Long.MIN_VALUE;
long min = Long.MAX_VALUE;
for(int n : pqOrderByDESC) {
if(dict.get(n) > 0) {
max = Math.max(max, n);
min = Math.min(min, n);
}
}
String res;
if(max == Long.MIN_VALUE) {
res = "EMPTY";
} else {
res = max + " " + min;
}
ans.append(res).append("\n");
}
System.out.println(ans);
}
}결과
헉 성공!
세번째 시도: 결과값 구하는 코드 개선
우선순위큐를 쓰는데 하나의 큐를 순회하고 있는게 영... 나쁘다.
그냥 두개의 큐에서 하나씩 빼주면서 유효값이면 break 걸어주도록 코드를 수정했다.
코드
위의 코드에서 결과 출력하는 구간만 다음과 같이 바꿨다.
long max = Long.MIN_VALUE;
long min = Long.MAX_VALUE;
while(!pqOrderByASC.isEmpty()) {
int key = pqOrderByASC.poll();
int tmp = dict.get(key);
if(tmp > 0) {
min = key;
break;
}
}
while(!pqOrderByDESC.isEmpty()) {
int key = pqOrderByDESC.poll();
int tmp = dict.get(key);
if(tmp > 0) {
max = key;
break;
}
}결과
이전보다 좀 줄었다.
마지막 코드 리팩토링
- 현재 코드에서는 큐에서 직접 찾아 제거하는데, dict 에서만 관리해줘도 된다.
- dict에서 원소를 제거하는 코드를 메서드로 분리한다. 중복 코드가 발생하기 때문.
코드
package solution;
import java.util.*;
import java.io.*;
public class BOJ7662_이중우선순위큐 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder ans = new StringBuilder();
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
PriorityQueue<Integer> pqOrderByASC = new PriorityQueue<>();
PriorityQueue<Integer> pqOrderByDESC = new PriorityQueue<>(Comparator.reverseOrder());
Map<Integer, Integer> dict = new HashMap<>(); // 키:큐의 들어간 원소값 값:몇 개 들어가있냐
int k = Integer.parseInt(br.readLine());
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
char op = st.nextToken().charAt(0);
int n = Integer.parseInt(st.nextToken());
if (op == 'I') {
// 두 큐에 n을 둘 다 넣고, dict 갱신한다.
pqOrderByDESC.offer(n);
pqOrderByASC.offer(n);
dict.put(n, dict.getOrDefault(n, 0) + 1);
} else {
if(dict.isEmpty()) continue;
if(n == 1) {
updateDict(pqOrderByDESC, dict);
} else {
updateDict(pqOrderByASC, dict);
}
}
}
String res;
if(dict.isEmpty()) {
res = "EMPTY";
} else {
int max = updateDict(pqOrderByDESC, dict);
int min = dict.isEmpty() ? max : updateDict(pqOrderByASC, dict);
res = max + " " + min;
}
ans.append(res).append("\n");
}
System.out.println(ans);
}
static int updateDict(PriorityQueue<Integer> pq, Map<Integer, Integer> dict) {
int num;
while(true) {
num = pq.poll();
int cnt = dict.getOrDefault(num, 0);
if(cnt == 0) continue;
if(cnt == 1) dict.remove(num);
else dict.replace(num, cnt - 1);
break;
}
return num;
}
}결과
시간 효율이 가장 좋다.
큐에서 원소를 제거하지 않고, dict 로 원소들을 관리해주기 때문.
마치며
어렵다.. 자료구조 적절하게 쓰는 것이 효율성에서 참 중요하다는 것을 느낀다.
개발의, 개발에 의한, 개발을 위한 기록장