https://www.acmicpc.net/problem/11286
정답률 56.720%
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0
-1
1
0
-1
-1
1
1
-2
2
0
N의 최대값이 으로 시간 복잡도의 알고리즘으로 풀 수 있다. 데이터가 삽입될 때마다 정렬이 필요하므로 우선순위 큐를 이용한다.
우선순위 큐만 구현하면 간단하게 조건에 따라 출력만 하면 된다. 람다로 우선순위 큐를 구현한다.
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
int absCompare = Integer.compare(Math.abs(o1), Math.abs(o2));
//절대값이 같지 않을 때
if (absCompare != 0) {
//절대값이 작은 수를 앞으로
return absCompare;
}
//절대값이 같을 때
else {
//작은 수를 앞으로
return Integer.compare(o1, o2);
}
});
//백준
public class Main {
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); //10^5
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
int absCompare = Integer.compare(Math.abs(o1), Math.abs(o2));
//절대값이 같지 않을 때
if (absCompare != 0) {
//절대값이 작은 수를 앞으로
return absCompare;
}
//절대값이 같을 때
else {
//작은 수를 앞으로
return Integer.compare(o1, o2);
}
});
for (int i = 0; i < N; i++) {
int x = Integer.parseInt(br.readLine());
if (x != 0) {
pq.add(x);
} else {
if (pq.isEmpty()) {
System.out.println(0);
} else {
System.out.println(pq.poll());
}
}
}
}
}