Coding Test/BOJ
[백준] 1655번 : 가운데를 말해요 (java)
Heang Lee
2021. 8. 22. 18:43
어떻게 생각하고 문제를 풀었는가?
최대 100,000 크기의 N에 대해 중간 값을 빠르게 구하기 위해서는 단순 탐색보다 빠른 탐색이 필요합니다.
중간 값이 대체될 경우 중간 값보다 작은 값들 중 최대 값과 큰 값들 중 최소 값 중 하나로 대체될 것입니다.
따라서 중간 값, 보다 작은 값들의 집합, 보다 큰 값들의 집합으로 나눔으로써 빠르게 중간 값을 구할 수 있을 것이라고 생각하였습니다.
코드
import java.io.*;
import java.util.Collections;
import java.util.PriorityQueue;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
int mid = Integer.parseInt(reader.readLine());
StringBuilder stringBuilder = new StringBuilder(String.valueOf(mid)).append("\n");
PriorityQueue<Integer> descQueue = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> ascQueue = new PriorityQueue<>();
for(int i=1; i<n; i++){
int value = Integer.parseInt(reader.readLine());
if(value > mid){
ascQueue.offer(value);
if(ascQueue.size() - descQueue.size()>1){
descQueue.offer(mid);
mid = ascQueue.poll();
}
}else{
descQueue.offer(value);
if(descQueue.size() > ascQueue.size()){
ascQueue.offer(mid);
mid = descQueue.poll();
}
}
stringBuilder.append(mid);
stringBuilder.append("\n");
}
reader.close();
System.out.println(stringBuilder);
}
}
우선 순위 큐 2개를 사용하여 보다 작은 값들의 집합, 보다 큰 값들의 집합을 정의하였습니다.
N줄에 걸쳐 입력되는 수들을 중간 값과 비교하여 우선 순위 큐에 삽입하고 중간 값을 우선 순위 큐에서 원소를 빼냄으로써 교체합니다.
보다 큰 값들을 담는 우선 순위 큐는 그렇지 않은 우선 순위 큐보다 최대 1개 더 많은 원소를 수용할 수 있는데, 이는 외친 수의 개수가 짝수 일경우 작은 수를 이야기 하여야 하기 때문입니다.