[백준]7662번 이중 우선순위 큐
일반적인 우선순위 큐는 우선순위가 가장 높은 데이터만을 추적한다.
하지만 이 이중 우선순위 큐는
- 우선순위가 가장 높은 데이터
- 우서누위가 가장 낮은 데이터
두 가지를 추적한다.
연산이 두 가지 있다.
- 데이터를 삽입
- 데이터를 삭제
- 우선순위가 가장 높은 것을 삭제
- 우선수위가 가장 낮은 것을 삭제
정수만 저장하는 이중 우선순위 큐 Q가 있다. 여기서 우선순위는 "정수의 값 "자체 라고 하자.
-
Q에 적용될 [ 일연의 연산 ] 이 주어질 때, 이를 처리한 후, 최종적으로 Q에 저장된 data중, 최대, 최소값을 출력하는 프로그램을 작성하자.
-
Q가 비어있는데 적용할 연산이 'D'라면 연산은 무시해도 된다.
-
제약조건🚀
- 각 테스트에 대한 연산의 개수는 100만 이하
-
출력해야 할 것 ?
- 모든 연산을 처리한 후 Q에 남아있는 값 중, 최대, 최소값
풀이 생각
-
우선순위 큐를 두 개 두면 되지 않나?—> 데이터의 동기화를 어떻게 관리할 것인가? + 데이터의 크기는 ?
- 이를 위해서는, 두 개의 우선순위 큐, 그리고 HashMap 이 필요할 것 같다.
- 우선순위 큐를 통해서 삽입, 제거 할 때, HashMap으로부터 개수를 확인 해야 한다.
- 삽입 : HashMAp에 해당 integer에 대한 값을 증가시킨다.
- 삭제 : HashMap 에서 , 해당 integer에 대한 값이 0보다 큰지 확인한다.
- 일단 해당 큐에서는 삭제한다.
- 삭제한 숫자가 이미 map에서는 0인 경우 → 큐에서, map에 매핑되는 값이 0보다 큰 값인 key값이 나올 때 까지 제거한다. ( map에서 매핑되는 값이 이미 0 인 경우에는, 다른쪽 큐에서 제거 했던 것이므로, 동기화를 위해 while문을 사용해 모두 제거한다)
-
남은 것 중 최대 최소는 ???
test마다 , lowQ에서 하나씩 꺼내보며, map에서 해당 key값에 매칭되는 값이 0보다 크다면, 해당 값이 min이고 0보다 큰 값이 나오자 마자 종료한다. highQ 또한 같고 여기서는 max다.
따라서 1개만이 남아있는 경우 그 값이 max이자 min이 되는 것이 가능하다.
public class Main{
public static long min=0,max=0;
public static boolean minFlag,maxFlag;
public static Map<Long,Long> map = new HashMap<>();
public static PriorityQueue<Long> lowQ = new PriorityQueue<>();// 내림차순
// 오름차순
public static PriorityQueue<Long> highQ = new PriorityQueue<>(Collections.reverseOrder());
public static void Setting() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// test의 개수
int test = Integer.parseInt(br.readLine());
int op=0;
String operation=null;
String[] ops= null;
long opnumb=0;
long numb=0;
long cur =0;
boolean flag = false;
for(int t=0;t<test;t++) {
lowQ.clear();
highQ.clear();
map.clear();
minFlag = false;
maxFlag = false;
// 연산의 개수
op = Integer.parseInt(br.readLine());
for (int o = 0; o < op; o++) {
// 각 연산
operation = br.readLine();
ops = operation.split(" ");
opnumb = Long.parseLong(ops[1]);
// Insert인 경우 -> 둘 다에 insert
if (ops[0].equals("I")) {
lowQ.add(opnumb);
highQ.add(opnumb);
cur = map.getOrDefault(opnumb, 0L);
cur++;
map.put(opnumb, cur);
} else {
flag = false;
if (opnumb == -1) {
while (lowQ.isEmpty() == false) {
numb = lowQ.poll();
if (map.get(numb) > 0) {
flag = true;
break;
}
}
} else {
// 1은 우선순위 최댓값을 삭제
while (highQ.isEmpty() == false) {
numb = highQ.poll();
if (map.get(numb) > 0) {
flag = true;
break;
}
}
}
// 실제로 지워진 수가 있는 경우 -> map에서도 수를 감소시킨다.
if (flag) {
cur = map.get(numb);
map.put(numb, cur - 1);
}
}
}
proProcessing();
if (minFlag == false) {
System.out.println("EMPTY");
continue;
} else {
System.out.println(max+" "+min);
}
}
}
// map에서 0인 것을 정리
public static void proProcessing(){
long low=0,high=0;
while(lowQ.isEmpty()==false){
low = lowQ.poll();
if(map.get(low)>0){
minFlag = true;
min =low;
break;
}
}
while(highQ.isEmpty()==false) {
high = highQ.poll();
if (map.get(high) > 0) {
max = high;
maxFlag=true;
break;
}
}
}
public static void main(String[] args) throws IOException {
Setting();
}
}
좋지 못한 코드같다.
다른 사람 풀이
다른 사람 풀이를 언뜻 보니 TreeMap을 사용했다.
아직까지 TreeMap자료구조를 사용해 본 적이 없었다.
오늘은 TreeMap에 대해 조금 살펴 본 후, 이 문제를 TreeMap 을 사용하는 방법으로 바꿔서 풀어보았다.
- 이 문제는 TreeMap만을 사용한다면,
- 가장 우선순위가 높은 것과, 낮은 것 모두를 O(logn)의 시간복잡도로 접근이 가능하다.
- pollFirstEntry() → the least key in this map 을 remvoe하고 return 한다.
- pollLastEntry() → the greates key in this map을 remove하고 return한다.
- remove(Object key) - mapping for this key인 것을 remove한다.
- firstEntry() → least key in this map 을 return한다.
- lastEntry() → greatest key in this map 을 return 한다.
map.put(1,1);
map.put(5,2);
map.put(2,3);
System.out.println(map.firstEntry()); // 1
System.out.println(map.lastEntry()); // 5import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
public static TreeMap<Long, Integer> map = new TreeMap<>();
public static void Setting() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int test = Integer.parseInt(br.readLine());
int numOfOp = 0; // test당 주어지는 연산의 개수
String op=null;
String[] ops =null;
long cur =0;
int curcnt=0;
for(int t=0;t<test;t++){
map.clear();
numOfOp = Integer.parseInt(br.readLine());
for(int o=0;o<numOfOp;o++){
op = br.readLine();
ops = op.split(" ");
cur = Long.parseLong(ops[1]);
if(ops[0].equals("I")){
curcnt = map.getOrDefault(cur, 0);
map.put(cur,curcnt+1);
}else {
if (map.isEmpty()) continue;
// 최소값을 삭제
if (cur == -1) {
Map.Entry<Long, Integer> entry = map.firstEntry();
if (entry.getValue() == 1) map.pollFirstEntry();
else map.put(entry.getKey(), entry.getValue() - 1);
}
// 최대값을 삭제
else {
Map.Entry<Long, Integer> entry = map.lastEntry();
if (entry.getValue() == 1) map.pollLastEntry();
else map.put(entry.getKey(), entry.getValue() - 1);
}
}
}
// 남은 것
if(map.isEmpty()) System.out.println("EMPTY");
else System.out.println(map.lastKey()+" "+map.firstKey());
}
}
public static void main(String[] args) throws IOException {
Setting();
}
}다른 사람 풀이를 보았다.
- 다시 보고 싶은 코드다. 아직 람다를 코테에 적용할 수준도 안 되는데 , 이 분 코드가 너무 깔끔하다. 이분을 기억해놓아야 겠다
import java.io.*;
import java.lang.reflect.InvocationTargetException;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class Main {
private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException, NoSuchMethodException, InvocationTargetException, IllegalAccessException {
int t = Integer.parseInt(reader.readLine());
while (t-- != 0) {
TreeMap<Integer, Integer> m = new TreeMap<>();
int n = Integer.parseInt(reader.readLine());
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(reader.readLine());
String op = st.nextToken();
int number = Integer.parseInt(st.nextToken());
switch (op) {
case "I":
m.merge(number, 1, Integer::sum);
break;
case "D":
if(m.isEmpty()) {
break;
}
int key = number == 1 ? m.lastKey() : m.firstKey();
m.computeIfPresent(key, (k, v) -> v - 1);
if(m.get(key) == 0) {
m.remove(key);
}
}
}
if(m.isEmpty()) {
writer.write("EMPTY\n");
} else {
writer.write(m.lastKey() + " " + m.firstKey() + "\n");
}
}
writer.flush();
writer.close();
}
}