๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/11279
- ๋๋ฆฌ ์ ์๋ ค์ง ์๋ฃ๊ตฌ์กฐ ์ค ์ต๋ ํ์ด ์๋ค. ์ต๋ ํ์ ์ด์ฉํ์ฌ ๋ค์๊ณผ ๊ฐ์ ์ฐ์ฐ์ ์ง์ํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ๋ฐฐ์ด์ ์์ฐ์ x๋ฅผ ๋ฃ๋๋ค.
- ๋ฐฐ์ด์์ ๊ฐ์ฅ ํฐ ๊ฐ์ ์ถ๋ ฅํ๊ณ , ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ค.
- ํ๋ก๊ทธ๋จ์ ์ฒ์์ ๋น์ด์๋ ๋ฐฐ์ด์์ ์์ํ๊ฒ ๋๋ค.
- ์ฒซ์งธ ์ค์ ์ฐ์ฐ์ ๊ฐ์ N(1 ≤ N ≤ 100,000)์ด ์ฃผ์ด์ง๋ค.
- ๋ค์ N๊ฐ์ ์ค์๋ ์ฐ์ฐ์ ๋ํ ์ ๋ณด๋ฅผ ๋ํ๋ด๋ ์ ์ x๊ฐ ์ฃผ์ด์ง๋ค. ๋ง์ฝ x๊ฐ ์์ฐ์๋ผ๋ฉด ๋ฐฐ์ด์ x๋ผ๋ ๊ฐ์ ๋ฃ๋(์ถ๊ฐํ๋) ์ฐ์ฐ์ด๊ณ , x๊ฐ 0์ด๋ผ๋ฉด ๋ฐฐ์ด์์ ๊ฐ์ฅ ํฐ ๊ฐ์ ์ถ๋ ฅํ๊ณ ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ ๊ฒฝ์ฐ์ด๋ค.
- ์ ๋ ฅ๋๋ ์์ฐ์๋ 231๋ณด๋ค ์๋ค.
- ์ ๋ ฅ์์ 0์ด ์ฃผ์ด์ง ํ์๋งํผ ๋ต์ ์ถ๋ ฅํ๋ค. ๋ง์ฝ ๋ฐฐ์ด์ด ๋น์ด ์๋ ๊ฒฝ์ฐ์ธ๋ฐ ๊ฐ์ฅ ํฐ ๊ฐ์ ์ถ๋ ฅํ๋ผ๊ณ ํ ๊ฒฝ์ฐ์๋ 0์ ์ถ๋ ฅํ๋ฉด ๋๋ค.
์์ด๋์ด
- PriorityQueue๋ฅผ ์ฌ์ฉํ์ฌ heap์ ๊ตฌํํ๋ค.
- ๊ธฐ๋ณธ heap์ ์ฐ์ ์์๊ฐ ๋ฎ์ ๊ฒ์ด ์ ์ผ ์์ ์ค๋ฏ๋ก ๋ฐ๋๋ก ์ ๋ ฌํ๋ฉด ์ฐ์ ์์๊ฐ ๋์ ๊ฒ์ด ์ ์ผ ์์ ์จ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- X
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ11279 {
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> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// ์ฐ์ฐ์ ๊ฐ์
int N = Integer.parseInt(br.readLine());
// ์ฐ์ฐ์ ๊ฐ์๋งํผ ๋ฐ๋ณต
for(int i = 0; i < N; i++){
int x = Integer.parseInt(br.readLine());
// ๋ง์ฝ ์
๋ ฅ๋ฐ์ ์๊ฐ 0์ผ๋
if(x == 0){
// maxHeap์ด ๋น์ด์๋ค๋ฉด
if(maxHeap.isEmpty()){
// 0์ ์ถ๋ ฅ
sb.append(0 + "\n");
}
// ๋ง์ฝ maxHeap์ด ๋น์ด์์ง ์๋ค๋ฉด
else{
// maxHeap์ ๊ผญ๋๊ธฐ ๊ฐ์ ์ถ๋ ฅํ๊ณ
sb.append(maxHeap.peek() + "\n");
// maxHeap์ ๋งจ ์์ ๊ฐ์ ์ ๊ฑฐ
maxHeap.poll();
}
}
// ๋ง์ฝ ์
๋ ฅ๋ฐ์ ์๊ฐ 0์ด ์๋๋ผ๋ฉด
else{
// maxHeap์ x๋ฅผ ์ถ๊ฐ
maxHeap.add(x);
}
}
System.out.println(sb);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 11724 ์ฐ๊ฒฐ ์์์ ๊ฐ์ (0) | 2024.08.13 |
---|---|
[Java] BOJ 2805 ๋๋ฌด ์๋ฅด๊ธฐ (2) | 2024.08.12 |
[Java] BOJ 2630 ์์ข ์ด ๋ง๋ค๊ธฐ (0) | 2024.08.05 |
[Java] BOJ 1541 ์์ด๋ฒ๋ฆฐ ๊ดํธ (0) | 2024.08.02 |
[Java] BOJ 1927 ์ต์ ํ (0) | 2024.08.01 |