๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/7662
- ์ด์ค ์ฐ์ ์์ ํ(dual priority queue)๋ ์ ํ์ ์ธ ์ฐ์ ์์ ํ์ฒ๋ผ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ , ์ญ์ ํ ์ ์๋ ์๋ฃ ๊ตฌ์กฐ์ด๋ค.
- ์ ํ์ ์ธ ํ์์ ์ฐจ์ด์ ์ ๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ ๋ ์ฐ์ฐ(operation) ๋ช ๋ น์ ๋ฐ๋ผ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๋ฐ์ดํฐ ๋๋ ๊ฐ์ฅ ๋ฎ์ ๋ฐ์ดํฐ ์ค ํ๋๋ฅผ ์ญ์ ํ๋ ์ ์ด๋ค.
- ์ด์ค ์ฐ์ ์์ ํ๋ฅผ ์ํด์ ๋ ๊ฐ์ง ์ฐ์ฐ์ด ์ฌ์ฉ๋๋๋ฐ, ํ๋๋ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ ํ๋ ์ฐ์ฐ์ด๊ณ ๋ค๋ฅธ ํ๋๋ ๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ๋ ์ฐ์ฐ์ด๋ค.
- ๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ๋ ์ฐ์ฐ์ ๋ ๋ ๊ฐ์ง๋ก ๊ตฌ๋ถ๋๋๋ฐ ํ๋๋ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๊ฒ์ ์ญ์ ํ๊ธฐ ์ํ ๊ฒ์ด๊ณ ๋ค๋ฅธ ํ๋๋ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋ฎ์ ๊ฒ์ ์ญ์ ํ๊ธฐ ์ํ ๊ฒ์ด๋ค.
- ์ ์๋ง ์ ์ฅํ๋ ์ด์ค ์ฐ์ ์์ ํ Q๊ฐ ์๋ค๊ณ ๊ฐ์ ํ์. Q์ ์ ์ฅ๋ ๊ฐ ์ ์์ ๊ฐ ์์ฒด๋ฅผ ์ฐ์ ์์๋ผ๊ณ ๊ฐ์ฃผํ์.
- Q์ ์ ์ฉ๋ ์ผ๋ จ์ ์ฐ์ฐ์ด ์ฃผ์ด์ง ๋ ์ด๋ฅผ ์ฒ๋ฆฌํ ํ ์ต์ข ์ ์ผ๋ก Q์ ์ ์ฅ๋ ๋ฐ์ดํฐ ์ค ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ผ.
- ์ ๋ ฅ ๋ฐ์ดํฐ๋ ํ์ค์ ๋ ฅ์ ์ฌ์ฉํ๋ค. ์ ๋ ฅ์ T๊ฐ์ ํ ์คํธ ๋ฐ์ดํฐ๋ก ๊ตฌ์ฑ๋๋ค.
- ์ ๋ ฅ์ ์ฒซ ๋ฒ์งธ ์ค์๋ ์ ๋ ฅ ๋ฐ์ดํฐ์ ์๋ฅผ ๋ํ๋ด๋ ์ ์ T๊ฐ ์ฃผ์ด์ง๋ค.
- ๊ฐ ํ ์คํธ ๋ฐ์ดํฐ์ ์ฒซ์งธ ์ค์๋ Q์ ์ ์ฉํ ์ฐ์ฐ์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ ์ k (k ≤ 1,000,000)๊ฐ ์ฃผ์ด์ง๋ค.
- ์ด์ด์ง๋ k ์ค ๊ฐ๊ฐ์ ์ฐ์ฐ์ ๋ํ๋ด๋ ๋ฌธ์(‘D’ ๋๋ ‘I’)์ ์ ์ n์ด ์ฃผ์ด์ง๋ค.
- ‘I n’์ ์ ์ n์ Q์ ์ฝ์ ํ๋ ์ฐ์ฐ์ ์๋ฏธํ๋ค. ๋์ผํ ์ ์๊ฐ ์ฝ์ ๋ ์ ์์์ ์ฐธ๊ณ ํ๊ธฐ ๋ฐ๋๋ค.
- ‘D 1’๋ Q์์ ์ต๋๊ฐ์ ์ญ์ ํ๋ ์ฐ์ฐ์ ์๋ฏธํ๋ฉฐ, ‘D -1’๋ Q ์์ ์ต์๊ฐ์ ์ญ์ ํ๋ ์ฐ์ฐ์ ์๋ฏธํ๋ค.
- ์ต๋๊ฐ(์ต์๊ฐ)์ ์ญ์ ํ๋ ์ฐ์ฐ์์ ์ต๋๊ฐ(์ต์๊ฐ)์ด ๋ ์ด์์ธ ๊ฒฝ์ฐ, ํ๋๋ง ์ญ์ ๋จ์ ์ ๋ ํ๊ธฐ ๋ฐ๋๋ค.
- ๋ง์ฝ Q๊ฐ ๋น์ด์๋๋ฐ ์ ์ฉํ ์ฐ์ฐ์ด ‘D’๋ผ๋ฉด ์ด ์ฐ์ฐ์ ๋ฌด์ํด๋ ์ข๋ค. Q์ ์ ์ฅ๋ ๋ชจ๋ ์ ์๋ -231 ์ด์ 231 ๋ฏธ๋ง์ธ ์ ์์ด๋ค.
- ์ถ๋ ฅ์ ํ์ค์ถ๋ ฅ์ ์ฌ์ฉํ๋ค. ๊ฐ ํ ์คํธ ๋ฐ์ดํฐ์ ๋ํด, ๋ชจ๋ ์ฐ์ฐ์ ์ฒ๋ฆฌํ ํ Q์ ๋จ์ ์๋ ๊ฐ ์ค ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ผ.
- ๋ ๊ฐ์ ํ ์ค์ ์ถ๋ ฅํ๋ ํ๋์ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถํ๋ผ. ๋ง์ฝ Q๊ฐ ๋น์ด์๋ค๋ฉด ‘EMPTY’๋ฅผ ์ถ๋ ฅํ๋ผ.
์์ด๋์ด
- PriorityQueue๋ฅผ 2๊ฐ ์ ์ธํด์ ํ๋๋ ์ต์๊ฐ ์ฐ์ Queue, ํ๋๋ ์ต๋๊ฐ ์ฐ์ Queue๋ก ์ฌ์ฉํ์๋ค.
- ๊ทธ๋ฆฌ๊ณ HashMap๋ฅผ ์ฌ์ฉํ์ฌ ์ ๋ ฅ๋ค์ด์ค๋ ๊ฐ๊ณผ ๊ทธ ๊ฐ์ด ๋ช๋ฒ ๋ค์ด์ค๋์ง๋ฅผ key๊ฐ๊ณผ value๊ฐ์ผ๋ก ์ ์ฅํ์๋ค.
- ์ฐ์ I๊ฐ ๋ค์ด์ค๋ฉด ๊ทธ ๋ค์ ์ซ์๋ฅผ Queue์ map์ ์ ์ฅํด์ค๋ค.
- D๊ฐ ๋ค์ด์ค๊ณ ๊ทธ ๋ค๊ฐ -1์ด๋ฉด ์ต์๊ฐ ์ฐ์ Queue์์ ๊ผญ๋๊ธฐ๊ฐ์ ๋นผ๊ณ HashMap์ ์๋ ๊ทธ ๊ฐ์(๊ผญ๋๊ธฐ๊ฐ) value๊ฐ์ ๊ธฐ์กด๊ฐ์์ -1ํ ๊ฐ์ผ๋ก ๊ฐฑ์ ์ํจ๋ค.
- ๋ง์ฝ 1์ด ๋ค์ด์ฌ ๊ฒฝ์ฐ์๋ ์ต๋๊ฐ ์ฐ์ Queue์์ ๊ผญ๋๊ธฐ๊ฐ์ ๋นผ๊ณ HashMap์ ์๋ ๊ทธ ๊ฐ์(๊ผญ๋๊ธฐ ๊ฐ) value๊ฐ์ ๊ธฐ์กด๊ฐ์์ -1ํ ๊ฐ์ผ๋ก ๊ฐฑ์ ์ํจ๋ค.
- ์ฌ๊ธฐ์ ๊ผญ๋๊ธฐ๊ฐ์ ๋นผ๊ธฐ์ ์ Queue๋ฅผ ์ต์ ํํด์ค์ผ๋๋๋ฐ, ๊ทธ ์ด์ ๋ ๋ง์ฝ ์ ๊ณ์ฐ์์ ์ต๋๊ฐ ์ฐ์ Queue์ ๊ผญ๋๊ธฐ ๊ฐ์ ๋บ์ ๋ ์ต์๊ฐ ์ฐ์ Queue์ ๊ผญ๋๊ธฐ์ ์กด์ฌํ ์๋ ์๊ธฐ ๋๋ฌธ์ด๋ค. (์ด ๋ง์ ์ต์๊ฐ ์ฐ์ Queue์ ์ต๋๊ฐ ์ฐ์ Queue๊ฐ ๊ฐ์์ผ ๋๋ค๋ ๋ป์ด ์๋ => ๋ฌธ์ ์์ ์ต๋๊ฐ๊ณผ ์ต์๊ฐ๋ง ๊ตฌํ๋ผ๊ณ ํ์๊ธฐ ๋๋ฌธ์ ๊ฐ Queue์ ๊ผญ๋๊ธฐ๊ฐ๋ง ์ต์ ํํด์ฃผ๋ฉฐ ๊ด๋ฆฌํ๋ฉด ๋จ)
- ๋ฐ๋ผ์ ๊ณ์ฐ์ ์ํ ๊ผญ๋๊ธฐ ๊ฐ์ ๋นผ๊ธฐ ์ , ๊ฐ Queue์ ๊ผญ๋๊ธฐ๊ฐ ์ต์ ํ๋ฅผ ํด์ค์ผํ๋ค.
- ์ต์ ํ๋ฅผ ํด์ฃผ๊ธฐ ์ํด ํจ์๋ฅผ ๋ฐ๋ก ๋ง๋ค์๋๋ฐ, PriorityQueue์ Hashmap์ ์ธ์๋ก ๋ฐ๊ณ while๋ฌธ์์ Queue๊ฐ ๋น๊ฑฐ๋ HashMap์์ ํด๋น Queue์ ๊ผญ๋๊ธฐ๊ฐ์ value๊ฐ 0์ด ์๋๊ฒ ๋ ๋๊น์ง ๋ฐ๋ณตํด์ฃผ๋ฉด ๋๋ ํจ์์ด๋ค. (value๊ฐ 0์ด๋ผ๋ฉด ์ด๋ฏธ ํด๋น ์๋ ์์ด์ก๋ค๋ ๋ป์ด๋ฏ๋ก Queue์์ ์ ๊ฑฐ๋ผ์ผํ๋ ์์ด๊ธฐ ๋๋ฌธ์ด๋ค.)
- ๋ชจ๋ ์ ๋ ฅ์ด ๋๋ ํ, ๊ฐ Queue๋ง๋ค ์ต์ ํ๋ฅผ ํ๋ฒ์ฉ ๋ํด์ฃผ๊ณ ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- ๋ฌธ์ ๋ฅผ ์๋ชป์ดํดํด์ ํ์ฐธ์ด ๊ฑธ๋ ธ๋ ๊ฒ ๊ฐ๋ค...
- Priority Queue๋ฅผ ์ฐ๋๋ฐ ์ต์๊ฐ ์ฐ์ Queue์ ์ต๋๊ฐ ์ฐ์ Queue๋ฅผ ์ด๋ป๊ฒ ๊ฐ๊ฒ ๋ง๋ค์ง์ ๋๋ฌด ๋งค๋ชฐ๋์ด ์์๋ ๊ฒ ๊ฐ๋ค...
- ๊ฐ์ ๊ผญ๋๊ธฐ์ ์์นํ ์ซ์๊ฐ ๋ค๋ฅธ๋ฐ ๋ฐ๋ํธ์์ ์ด๋ป๊ฒ ์ซ์๋ฅผ ๊บผ๋ด์ง ์ด๋ฐ์๊ฐ์ ํ๋๋ผ ์๊ฐ ๋ญ๋น๋ฅผ ํ๋ค..ใ ใ
- ์ฌ์ค ์ฒ์์๋ PriorityQueue ๋๊ฐ๋ฅผ ์์ฐ๊ณ ํ๋ ค๊ณ ํ๋๋ฐ ๊ทธ๊ฑด ์๋๊ณ ... Priority Queue๋ฅผ ๋๊ฐ์ฐ๋ ๋ค๋ฅธ ๋ฐฉ๋ฒ์ ์ฒ์์ ์ ์ถํ๋ค๊ฐ ์๊ฐ์ด๊ณผ๋์ ์ ๋ฐฉ๋ฒ์ผ๋ก ํ๊ฒ ๋์๋ค... (remove ํจ์๊ฐ ์๊ฐ์ ๊ทธ๋ ๊ฒ ๋ง์ด ์ก์๋จน๋์ค ๋ชฐ๋๋ค..ใ ใ )
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ7662 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int testCase = 0; testCase < T; testCase++){
int N = Integer.parseInt(br.readLine());
// ์ต์๊ฐ์ ์ฐ์ ์ผ๋ก ์ฐ์ ์์ ์ ์ฅ
PriorityQueue<Integer> minQ = new PriorityQueue<>();
// ์ต๋๊ฐ์ ์ฐ์ ์ผ๋ก ์ฐ์ ์์ ์ ์ฅ
PriorityQueue<Integer> maxQ = new PriorityQueue<>(Comparator.reverseOrder());
// ์ญ์ ๊ฐ์ ์ ์ฅํ Hashmap
HashMap<Integer, Integer> cnt = new HashMap<>();
for(int i = 0; i < N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
// ์ฐ์ฐ ์ข
๋ฅ
char cal = st.nextToken().charAt(0);
// ์ซ์
int n = Integer.parseInt(st.nextToken());
// ์ซ์๋ฅผ ์
๋ ฅํด์ผ ๋ ๋๋ฉด
if(cal == 'I'){
// ์ซ์๋ฅผ Priority Queue์ ๊ฐ๊ฐ ์ ์ฅ
minQ.offer(n);
maxQ.offer(n);
// ์ซ์๋ค์ ๊ฐ์๋ฅผ ์ ์ฅ
cnt.put(n, cnt.getOrDefault(n, 0) + 1);
}
// ์ซ์๋ฅผ ๋นผ์ผ ๋ ๋
else if(cal == 'D'){
// ์ซ์๊ฐ -1์ด๋ผ๋ฉด ์ต์๊ฐ์ ๋นผ์ผ๋จ
if(n == -1){
// ์ต์๊ฐ์ ์ ๊ฑฐํ๊ธฐ ์ ์ต์ ํ๋ฅผ ํ๋ฒ ํด์ค
remove(minQ, cnt);
// Queue๊ฐ ๋น ๊ฐ์ด ์๋ ๋
if(!minQ.isEmpty()){
int num = minQ.peek();
// ์ต์๊ฐ Queue์์ ์ ์ผ ์์ ์๋ ๊ฐ์ ์ ๊ฑฐ ํ,
minQ.poll();
// ํด๋น ๊ฐ๊ณผ ํด๋น ๊ฐ์ value์ 1์ ๋บ ๊ฐ์
// Hashmap์ ์ฌ์ ์ฅ
cnt.put(num, cnt.get(num) - 1);
}
}
// ์ซ์๊ฐ 1์ด๋ผ๋ฉด ์ต๋๊ฐ์ ๋นผ์ผ๋๋ฏ๋ก
else if(n == 1) {
// ์ต๋๊ฐ์ ์ ๊ฑฐํ๊ธฐ ์ ์ต์ ํ๋ฅผ ํ๋ฒ ํด์ค
remove(maxQ, cnt);
// Queue๊ฐ ๋น ๊ฐ์ด ์๋ ๋
if(!maxQ.isEmpty()){
int num = maxQ.peek();
// ์ต๋๊ฐ Queue์์ ์ ์ผ ์์ ์๋ ๊ฐ์ ์ ๊ฑฐ ํ,
maxQ.poll();
// ํด๋น ๊ฐ๊ณผ ํด๋น ๊ฐ์ value์ 1์ ๋บ ๊ฐ์
// Hashmap์ ์ฌ์ ์ฅ
cnt.put(num, cnt.get(num) - 1);
}
}
}
}
// ์ต์ข
์ ์ผ๋ก ์ถ๋ ฅํ๊ธฐ ์ , ๊ฐ Queue ์ต์ ํ๋ฅผ ํด์ค
remove(minQ, cnt);
remove(maxQ, cnt);
// ๋ง์ฝ ๋ชจ๋ ๊ณ์ฐ์ด ๋๋ฌ์ ๋ Deque๊ฐ ๋น์ด์๋ค๋ฉด
if(minQ.isEmpty()){
sb.append("EMPTY" + "\n");
}
// ๋น์ด์์ง์๋ค๋ฉด ์ต์๊ฐ๊ณผ ์ต๋๊ฐ์ ์ถ๋ ฅ
else{
sb.append(maxQ.peek() + " " + minQ.peek() + "\n");
}
}
System.out.println(sb);
}
// ์ซ์๊ฐ ์ญ์ ๋๊ฒ ๋ค๋ฅธ Queue์ ๋จ์์์ผ๋ฉด ์ ๊ฑฐํ ํจ์
public static void remove(PriorityQueue<Integer> queue, HashMap<Integer, Integer> count){
// Queue๊ฐ ๋น๋๊น์ง ๊ทธ๋ฆฌ๊ณ
// Queue์ ๊ผญ๋๊ธฐ์ ์๋ ๊ฐ์ ๋ํ value๊ฐ 0์ด ์๋๊ธฐ ์ ๊น์ง ๋ฐ๋ณต
// ์๋ฅผ ๋ค์ด,
// maxQ์์ ์ ๊ฑฐํ ๊ฐ์ด minQ์์ ์ ๊ฑฐ๊ฐ ์๋์ ์๋ ์์ผ๋ฏ๋ก
// minQ์์ ๊ผญ๋๊ธฐ๊ฐ์ ๋ํ value๊ฐ์ HashMap์์ ํ์ธํ์ ๋
// 0์ผ ๊ฒฝ์ฐ, maxQ์์ ์ด๋ฏธ ์์ด๋ค๋ ๋ป์ด๋ฏ๋ก minQ์์ ๊ผญ๋๊ธฐ๊ฐ์ ์ ๊ฑฐ
// ์ด์ฐจํผ ์ ์ผ ํฐ ๊ฐ๊ณผ ์ ์ผ ์์ ๊ฐ๋ง ์ถ๋ ฅํ๋ฉด ๋๊ธฐ ๋๋ฌธ์
// minQ์ maxQ์ ๊ผญ๋๊ธฐ๊ฐ๋ง ์ต์ ํ๋ฅผ ์ ์งํ๋ฉด ๋จ
while (!queue.isEmpty() && count.get(queue.peek()) == 0) {
queue.poll();
}
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 16928 ๋ฑ๊ณผ ์ฌ๋ค๋ฆฌ ๊ฒ์ (10) | 2024.09.07 |
---|---|
[Java] BOJ 7576 ํ ๋งํ (0) | 2024.09.02 |
[Java] BOJ 7569 ํ ๋งํ (0) | 2024.09.01 |
[Java] BOJ 5430 AC (4) | 2024.08.31 |
[Java] BOJ 14940 ์ฌ์ด ์ต๋จ๊ฑฐ๋ฆฌ (8) | 2024.08.28 |