๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1927
- ๋๋ฆฌ ์ ์๋ ค์ง ์๋ฃ๊ตฌ์กฐ ์ค ์ต์ ํ์ด ์๋ค. ์ต์ ํ์ ์ด์ฉํ์ฌ ๋ค์๊ณผ ๊ฐ์ ์ฐ์ฐ์ ์ง์ํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ๋ฐฐ์ด์ ์์ฐ์ x๋ฅผ ๋ฃ๋๋ค.
- ๋ฐฐ์ด์์ ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๊ณ , ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ค.
- ํ๋ก๊ทธ๋จ์ ์ฒ์์ ๋น์ด์๋ ๋ฐฐ์ด์์ ์์ํ๊ฒ ๋๋ค.
- ์ฒซ์งธ ์ค์ ์ฐ์ฐ์ ๊ฐ์ N(1 ≤ N ≤ 100,000)์ด ์ฃผ์ด์ง๋ค.
- ๋ค์ N๊ฐ์ ์ค์๋ ์ฐ์ฐ์ ๋ํ ์ ๋ณด๋ฅผ ๋ํ๋ด๋ ์ ์ x๊ฐ ์ฃผ์ด์ง๋ค.
- ๋ง์ฝ x๊ฐ ์์ฐ์๋ผ๋ฉด ๋ฐฐ์ด์ x๋ผ๋ ๊ฐ์ ๋ฃ๋(์ถ๊ฐํ๋) ์ฐ์ฐ์ด๊ณ , x๊ฐ 0์ด๋ผ๋ฉด ๋ฐฐ์ด์์ ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๊ณ ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ ๊ฒฝ์ฐ์ด๋ค.
- x๋ 231๋ณด๋ค ์์ ์์ฐ์ ๋๋ 0์ด๊ณ , ์์ ์ ์๋ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง์ง ์๋๋ค.
- ์ ๋ ฅ์์ 0์ด ์ฃผ์ด์ง ํ์๋งํผ ๋ต์ ์ถ๋ ฅํ๋ค.
- ๋ง์ฝ ๋ฐฐ์ด์ด ๋น์ด ์๋ ๊ฒฝ์ฐ์ธ๋ฐ ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๋ผ๊ณ ํ ๊ฒฝ์ฐ์๋ 0์ ์ถ๋ ฅํ๋ฉด ๋๋ค.
์์ด๋์ด
- ์ต์ ํ ๋ฌธ์ ๊ฐ PriorityQueue๋ฅผ ์ค๋ช ํ๊ณ ์๋ค๊ณ ์๊ฐํ๋ค.
- Priority Queue๊ฐ ์ฐ์ ์์ ํ๋ก, ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋ฎ์ ๊ฐ์ด ๋จผ์ ๋์ค๊ฒ ๋์ด์๋๋ฐ, ์ด ๋ฌธ์ ์์ Integer๋ฅผ ๋ฃ์์ ๋ ์ซ์๊ฐ ์์ ์๋ก ์ฐ์ ์์๊ฐ ๋ฎ๋ค๊ณ ํ๋จ๋์ด ์๋ก ์ฌ๋ผ๊ฐ๋ค.
- ๋ฐ๋ผ์ ๋งจ ์์ ๊ฐ์ด ์ต์๊ฐ์ด ๋๋ค๊ณ ํ ์ ์๋ค.
- ๋ฐ๋ผ์ 0์ด ๋ค์ด์์๋ PriorityQueue๊ฐ ๋น์ด์๋ค๋ฉด 0์ ์ถ๋ ฅํ๊ฒํ๊ณ ๋น์ด์์ง ์๋ค๋ฉด PriorityQueue์ ๋งจ ์ ๊ฐ์ ์ถ๋ ฅํ๋ค.
- ๊ทธ๋ฆฌ๊ณ ๋ค๋ฅธ ์ซ์๊ฐ ๋ค์ด์ค๋ฉด PriorityQueue์ ๋ฃ๋๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- X
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ1927 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// ์ปฌ๋ ์
์ ๋ฐ์ดํฐ๋ฅผ ๋ฃ์ผ๋ฉด remove๋๋ peek์ ๊ฐ์ด minHeap์ ์ต์๊ฐ์ด ๋จ
// Primary Queue๋ ์ฐ์ ์์ ํ๋ก ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋ฎ์ ๊ฐ์ด ๋จผ์ ๋์ค๊ฒ ๋์ด์์
// ์ฐ์ ์์๊ฐ ๋ฎ๋ค๋ ๊ฒ์ Integer๋ฅผ ๋ฃ์์ ๋, ์ต์๊ฐ์ผ๋ก ํ๋จ๋จ
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// ์ฐ์ฐ์ ๊ฐ์
int N = Integer.parseInt(br.readLine());
// ์ฐ์ฐ์ ๊ฐ์๋งํผ ๋ฐ๋ณต
for(int i = 0; i < N; i++){
int x = Integer.parseInt(br.readLine());
// ๋ง์ฝ ์
๋ ฅ๋ฐ์ ์๊ฐ 0์ผ๋
if(x == 0){
// minHeap์ด ๋น์ด์๋ค๋ฉด
if(minHeap.isEmpty()){
// 0์ ์ถ๋ ฅ
sb.append(0 + "\n");
}
// ๋ง์ฝ minHeap์ด ๋น์ด์์ง ์๋ค๋ฉด
else{
// minHeap์ ๊ผญ๋๊ธฐ ๊ฐ์ ์ถ๋ ฅํ๊ณ
sb.append(minHeap.peek() + "\n");
// minHeap์ ๋งจ ์์ ๊ฐ์ ์ ๊ฑฐ
minHeap.poll();
}
}
// ๋ง์ฝ ์
๋ ฅ๋ฐ์ ์๊ฐ 0์ด ์๋๋ผ๋ฉด
else{
// minHeap์ x๋ฅผ ์ถ๊ฐ
minHeap.add(x);
}
}
System.out.println(sb);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 2630 ์์ข ์ด ๋ง๋ค๊ธฐ (0) | 2024.08.05 |
---|---|
[Java] BOJ 1541 ์์ด๋ฒ๋ฆฐ ๊ดํธ (0) | 2024.08.02 |
[Java] BOJ 1260 DFS์ BFS (0) | 2024.08.01 |
[Java] BOJ 1012 ์ ๊ธฐ๋ ๋ฐฐ์ถ (0) | 2024.07.31 |
[Java] BOJ 7626 Four Squares (2) | 2024.07.31 |