๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/11286
- ์ ๋๊ฐ ํ์ ๋ค์๊ณผ ๊ฐ์ ์ฐ์ฐ์ ์ง์ํ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
- ๋ฐฐ์ด์ ์ ์ x (x ≠ 0)๋ฅผ ๋ฃ๋๋ค.
- ๋ฐฐ์ด์์ ์ ๋๊ฐ์ด ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๊ณ , ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ค. ์ ๋๊ฐ์ด ๊ฐ์ฅ ์์ ๊ฐ์ด ์ฌ๋ฌ๊ฐ์ผ ๋๋, ๊ฐ์ฅ ์์ ์๋ฅผ ์ถ๋ ฅํ๊ณ , ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ค.
- ํ๋ก๊ทธ๋จ์ ์ฒ์์ ๋น์ด์๋ ๋ฐฐ์ด์์ ์์ํ๊ฒ ๋๋ค.
- ์ฒซ์งธ ์ค์ ์ฐ์ฐ์ ๊ฐ์ N(1≤N≤100,000)์ด ์ฃผ์ด์ง๋ค.
- ๋ค์ N๊ฐ์ ์ค์๋ ์ฐ์ฐ์ ๋ํ ์ ๋ณด๋ฅผ ๋ํ๋ด๋ ์ ์ x๊ฐ ์ฃผ์ด์ง๋ค.
- ๋ง์ฝ x๊ฐ 0์ด ์๋๋ผ๋ฉด ๋ฐฐ์ด์ x๋ผ๋ ๊ฐ์ ๋ฃ๋(์ถ๊ฐํ๋) ์ฐ์ฐ์ด๊ณ , x๊ฐ 0์ด๋ผ๋ฉด ๋ฐฐ์ด์์ ์ ๋๊ฐ์ด ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๊ณ ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ ๊ฒฝ์ฐ์ด๋ค. ์ ๋ ฅ๋๋ ์ ์๋ -2^31๋ณด๋ค ํฌ๊ณ , 2^31๋ณด๋ค ์๋ค.
-
์ ๋ ฅ์์ 0์ด ์ฃผ์ด์ง ํ์๋งํผ ๋ต์ ์ถ๋ ฅํ๋ค. ๋ง์ฝ ๋ฐฐ์ด์ด ๋น์ด ์๋ ๊ฒฝ์ฐ์ธ๋ฐ ์ ๋๊ฐ์ด ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๋ผ๊ณ ํ ๊ฒฝ์ฐ์๋ 0์ ์ถ๋ ฅํ๋ฉด ๋๋ค.
์์ด๋์ด
- ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ์ฌ ์ฐ์ ์์๊ฐ ๋ฎ์ ์์๋๋ก ์ ๋ ฌํ๋ค.
- ๊ทธ๋ฆฌ๊ณ point๋ฅผ ์ฌ์ฉํ์ฌ ์ ๋๊ฐ๊ณผ ์๋ ์๋ฅผ PriorityQueue์ ์ ์ฅํ๋ค.
- Compare์ ์ฌ์ฉํ์ฌ ์ ๋๊ฐ์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ๊ณ ์ ๋๊ฐ์ด ๊ฐ๋ค๋ฉด ์๋์๋ฅผ ๋น๊ตํด์ ์ ๋ ฌํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- Compare์ ๋ฐฉ๋ฒ์ด ์ ์๊ฐ๋์ง ์์์ ๋ค์ ์ฐพ์๋ณด๊ณ ๊ณต๋ถํ๋ค...
์ฝ๋
import java.io.*;
import java.util.*;
import java.awt.*;
public class BOJ11286 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// ์ฐ์ฐ์ ๊ฐ์
int N = Integer.parseInt(br.readLine());
// ์ ๋๊ฐ๊ณผ ๊ทธ๋ฅ ์๋ฅผ ์ ์ฅํ ์ฐ์ ์์ ํ
// ์ ๋๊ฐ์ ๊ธฐ์ค์ผ๋ก ๋จผ์ ์ ๋ ฌํ๊ณ ๊ธฐ์กด๊ฐ์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํจ
PriorityQueue<Point> q = new PriorityQueue<Point>(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
// ์ ๋๊ฐ์ด ๋ ์์ ์์ผ๋ก ์ ๋ ฌ
if(o1.x < o2.x){
return -1;
}
else if(o1.x > o2.x){
return 1;
}
// ๋ง์ฝ ์ ๋๊ฐ์ด ๊ฐ๋ค๋ฉด
// ์ ๋๊ฐ์ ๋ง๋ค๊ธฐ ์ ์ ์๋ ์ซ์๋ก
// ๋ ์์ ์์ผ๋ก ์ ๋ ฌ
else{
if(o1.y < o2.y){
return -1;
}
else if(o1.y > o2.y){
return 1;
}
else{
return 0;
}
}
}
});
for(int i = 0; i < N; i++){
// ์
๋ ฅ๋ฐ์ ์
int n = Integer.parseInt(br.readLine());
// ๋ง์ฝ ์
๋ ฅ๋ฐ์ ์๊ฐ 0์ด๊ณ
if(n == 0){
// ํ๊ฐ ๋น์๋ค๋ฉด
if(q.isEmpty()){
// 0์ ์ถ๋ ฅํ๊ณ
sb.append(0 + "\n");
}
// ํ๊ฐ ๋น์ง ์์๋ค๋ฉด
else{
// ํ์ ์ ์ฅ๋์ด ์๋
// ๋งจ ์์ ์๋ ์๋ฅผ ์ ์ฅ ํ
int out = q.peek().y;
// ํ์์ ๋นผ๋ด๊ณ
q.poll();
// ์ถ๋ ฅ
sb.append(out + "\n");
}
}
// ์
๋ ฅ๋ฐ์ ์๊ฐ 0์ด ์๋๋ผ๋ฉด
else{
// ์
๋ ฅ๋ฐ์ ์์ ์ ๋๊ฐ์ผ๋ก ๋ณํํ์ฌ ์ ์ฅ ํ,
int n_abs = Math.abs(n);
// ์ฐ์ ์์ ํ์ ์ ๋๊ฐ๊ณผ ์๋ ์๋ฅผ ์ ์ฅ
q.offer(new Point(n_abs, n));
}
}
System.out.println(sb);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 14940 ์ฌ์ด ์ต๋จ๊ฑฐ๋ฆฌ (8) | 2024.08.28 |
---|---|
[Java] BOJ 11403 ๊ฒฝ๋ก ์ฐพ๊ธฐ (0) | 2024.08.27 |
[Java] BOJ 6064 ์นด์ ๋ฌ๋ ฅ (0) | 2024.08.25 |
[Java] BOJ 5525 IOIOI (0) | 2024.08.24 |
[Java] BOJ 2667 ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ (0) | 2024.08.23 |