1655번: 가운데를 말해요
첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
수빈이가 동생에게 숫자를 하나씩 부를 때마다 동생이 처음에 말한 수부터 현재 말한 수까지의 중간 값을 출력해야합니다.
이 문제는 우선순위 큐로 해결할 수 있습니다.
저는 우선순위 큐 2개(최대 힙, 최소 힙 각각 1개)를 사용하였습니다.
최대 힙에는 작은값들, 최소 힙에는 큰 값들을 저장합니다. 그리고 출력은 최대힙에서 가장 작은 수를 출력합니다.
출력을 최대 힙으로 사용하기 때문에 최대 힙의 크기를 더 크게 유지시킵니다.
하지만 중간 값을 구해야하기 때문에 최대 힙과 최소 힙의 크기를 같게 하거나 최대 힙의 크기가 1만큼 더 커야합니다.
우선 최대 힙이 비어있으면 최대 힙에 저장합니다.
그리고 최대 힙의 크기가 최소 힙과 같으면 최대 힙에 add
최소 힙의 크기가 더 작으면 최소 힙에 add를 해줍니다.
이 과정 이후에 최소 힙의 가장 작은 값이 최대 힙의 가장 큰 값보다 작으면 두 수를 교환합니다.
마지막에는 최대 힙에서 가장 큰 수를 출력하면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static int list[];
static int N;
static void func() {
PriorityQueue<Integer> maxq = new PriorityQueue<>();
PriorityQueue<Integer> minq = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
int x = list[i];
if (maxq.isEmpty()) {
maxq.add(-x);
sb.append(-maxq.peek() + "\n");
continue;
}
if (maxq.size() == minq.size())
maxq.add(-x);
else
minq.add(x);
if (-maxq.peek() > minq.peek()) {
int a = -maxq.peek();
int b = -minq.peek();
maxq.remove();
minq.remove();
maxq.add(b);
minq.add(a);
}
sb.append(-maxq.peek() + "\n");
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = Integer.parseInt(st.nextToken());
}
}
public static void main(String[] args) throws Exception {
input();
func();
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 2164 카드2 (0) | 2021.02.01 |
|---|---|
| boj 10845 큐 (0) | 2021.02.01 |
| boj 11279 최대 힙 (0) | 2021.01.31 |
| boj 1927 최소 힙 (0) | 2021.01.31 |
| boj 4889 안정적인 문자열 (0) | 2021.01.26 |