๋๋ฆฌ ์ ์๋ ค์ง ์๋ฃ๊ตฌ์กฐ ์ค ์ต์ ํ์ด ์๋ค. ์ต์ ํ์ ์ด์ฉํ์ฌ ๋ค์๊ณผ ๊ฐ์ ์ฐ์ฐ์ ์ง์ํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋ฐฐ์ด์ ์์ฐ์ x๋ฅผ ๋ฃ๋๋ค.
๋ฐฐ์ด์์ ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๊ณ , ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ค.
ํ๋ก๊ทธ๋จ์ ์ฒ์์ ๋น์ด์๋ ๋ฐฐ์ด์์ ์์ํ๊ฒ ๋๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ฐ์ฐ์ ๊ฐ์ N(1 โค N โค 100,000)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ ์ฐ์ฐ์ ๋ํ ์ ๋ณด๋ฅผ ๋ํ๋ด๋ ์ ์ x๊ฐ ์ฃผ์ด์ง๋ค. ๋ง์ฝ x๊ฐ ์์ฐ์๋ผ๋ฉด ๋ฐฐ์ด์ x๋ผ๋ ๊ฐ์ ๋ฃ๋(์ถ๊ฐํ๋) ์ฐ์ฐ์ด๊ณ , x๊ฐ 0์ด๋ผ๋ฉด ๋ฐฐ์ด์์ ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๊ณ ๊ทธ ๊ฐ์ ๋ฐฐ์ด์์ ์ ๊ฑฐํ๋ ๊ฒฝ์ฐ์ด๋ค. x๋ 231๋ณด๋ค ์์ ์์ฐ์ ๋๋ 0์ด๊ณ , ์์ ์ ์๋ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง์ง ์๋๋ค.
์ถ๋ ฅ
์ ๋ ฅ์์ 0์ด ์ฃผ์ด์ง ํ์๋งํผ ๋ต์ ์ถ๋ ฅํ๋ค. ๋ง์ฝ ๋ฐฐ์ด์ด ๋น์ด ์๋ ๊ฒฝ์ฐ์ธ๋ฐ ๊ฐ์ฅ ์์ ๊ฐ์ ์ถ๋ ฅํ๋ผ๊ณ ํ ๊ฒฝ์ฐ์๋ 0์ ์ถ๋ ฅํ๋ฉด ๋๋ค.
๐ก ์ฐ์ ์์ ํ ์ฌ์ฉ
๐ก 0์ด๊ณ ํ๊ฐ ๋น์ด์์ผ๋ฉด 0์ list์ ๋ฃ๊ณ , ํ๊ฐ ์ ๋น์ด์์ผ๋ฉด ํ์ ์ต์๊ฐ์ ๋บ
๐ก 0์ด ์๋๋ฉด ํ์ ์ซ์๋ฅผ ๋ฃ์
PriorityQueue<Integer> pq = new PriorityQueue<>();
if(tmp == 0) {
if(pq.isEmpty()) {
list.add(0);
} else {
list.add(pq.poll());
}
}
else {
pq.add(tmp);
}
import java.util.*;
import java.io.*;
public class BOJ_1927 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PriorityQueue<Integer> pq = new PriorityQueue<>();
ArrayList<Integer> list = new ArrayList<>();
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++) {
int tmp = Integer.parseInt(br.readLine());
if(tmp == 0) {
if(pq.isEmpty()) {
list.add(0);
} else {
list.add(pq.poll());
}
} else {
pq.add(tmp);
}
}
for(int i : list) {
System.out.println(i);
}
}
}
์ฑ๊ณตโจ