์ ๋๊ฐ ํ์ ๋ค์๊ณผ ๊ฐ์ ์ฐ์ฐ์ ์ง์ํ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
1. ๋ฐฐ์ด์ ์ ์ x (xย โ 0)๋ฅผ ๋ฃ๋๋ค.
2. ๋ฐฐ์ด์์ ์ ๋๊ฐ์ด ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๊ณ , ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ค. ์ ๋๊ฐ์ด ๊ฐ์ฅ ์์ ๊ฐ์ด ์ฌ๋ฌ๊ฐ์ผ ๋๋, ๊ฐ์ฅ ์์ ์๋ฅผ ์ถ๋ ฅํ๊ณ , ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ค.
ํ๋ก๊ทธ๋จ์ ์ฒ์์ ๋น์ด์๋ ๋ฐฐ์ด์์ ์์ํ๊ฒ ๋๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ฐ์ฐ์ ๊ฐ์ N(1โคNโค100,000)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ ์ฐ์ฐ์ ๋ํ ์ ๋ณด๋ฅผ ๋ํ๋ด๋ ์ ์ x๊ฐ ์ฃผ์ด์ง๋ค. ๋ง์ฝ x๊ฐ 0์ด ์๋๋ผ๋ฉดย ๋ฐฐ์ด์ x๋ผ๋ ๊ฐ์ ๋ฃ๋(์ถ๊ฐํ๋) ์ฐ์ฐ์ด๊ณ , x๊ฐ 0์ด๋ผ๋ฉด ๋ฐฐ์ด์์ ์ ๋๊ฐ์ด ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๊ณ ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ ๊ฒฝ์ฐ์ด๋ค. ์ ๋ ฅ๋๋ ์ ์๋ -231๋ณด๋ค ํฌ๊ณ ,ย 231๋ณด๋ค ์๋ค.
์ถ๋ ฅ
์ ๋ ฅ์์ 0์ด ์ฃผ์ด์ง ํ์๋งํผ ๋ต์ ์ถ๋ ฅํ๋ค. ๋ง์ฝ ๋ฐฐ์ด์ด ๋น์ด ์๋ ๊ฒฝ์ฐ์ธ๋ฐ ์ ๋๊ฐ์ด ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๋ผ๊ณ ํ ๊ฒฝ์ฐ์๋ 0์ ์ถ๋ ฅํ๋ฉด ๋๋ค.
๐ก ์ฐ์ ์์ ํ ์ฌ์ฉ
๐ก ์ ๋๊ฐ๊ณผ ์๋๊ฐ์ ์ ์ฅํ class ๊ตฌํ
comparable์ ํตํด ์ ๋๊ฐ ๊ธฐ์ค ์ค๋ฆ์ฐจ์ ์ ๋ ฌ (์ ๋๊ฐ์ด ๊ฐ๋ค๋ฉด ์๋๊ฐ ์ค๋ฆ์ฐจ์)
๐ก ์
๋ ฅ์ด 0์ด ์๋๋ฉด, ์๋ฅผ ์ฐ์ ์์ ํ์ ๋ฃ์
๐ก 0์ธ ๊ฒฝ์ฐ, ํ๊ฐ ๋น๋ฉด 0์ถ๋ ฅ ์๋๋ผ๋ฉด ํ์์ ํ๋ ๊บผ๋ด์ ์ถ๋ ฅ
PriorityQueue<Abs> pq = new PriorityQueue<>();
static class Abs implements Comparable<Abs>{
int abs;
int origin;
Abs(int abs, int origin){
this.abs = abs;
this.origin = origin;
}
@Override
public int compareTo(Abs o) {
if(this.abs == o.abs)
return this.origin - o.origin;
return this.abs - o.abs;
}
}
if(tmp != 0) {
pq.add(new Abs(Math.abs(tmp), tmp));
}
else {
if(pq.isEmpty()) {
sb.append("0");
} else {
sb.append(Integer.toString(pq.poll().origin));
}
sb.append("\n");
}
import java.util.PriorityQueue;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class BOJ_11286 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
PriorityQueue<Abs> pq = new PriorityQueue<>();
while(n-->0) {
int tmp = Integer.parseInt(br.readLine());
if(tmp != 0) {
pq.add(new Abs(Math.abs(tmp), tmp));
} else {
if(pq.isEmpty()) {
sb.append("0");
} else {
sb.append(Integer.toString(pq.poll().origin));
}
sb.append("\n");
}
}
bw.write(sb.toString());
bw.flush();
bw.close();
}
static class Abs implements Comparable<Abs>{
int abs;
int origin;
Abs(int abs, int origin){
this.abs = abs;
this.origin = origin;
}
@Override
public int compareTo(Abs o) {
if(this.abs == o.abs)
return this.origin - o.origin;
return this.abs - o.abs;
}
}
}
์ฑ๊ณตโจ