BOJ 1165
위 문제는 백준 사이트의 알고리즘 1165 문제에 관한 설명입니다.
문제
수빈이는 동생에게 “가운데를 말해요” 게임을 가르쳐주고 있다.
수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다.
만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면,
동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다.
수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다.
N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다.
그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다.
정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.
출력
한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.
package PQ;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
public class BOJ1655 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
int N = Integer.parseInt(br.readLine());
for(int i = 0 ; i < N; i++) {
int Number = Integer.parseInt(br.readLine());
if(minHeap.size() == maxHeap.size()) {
maxHeap.offer(Number);
}else {
minHeap.offer(Number);
}
if(!minHeap.isEmpty() && ! maxHeap.isEmpty()) {
if(minHeap.peek() < maxHeap.peek()) {
int temp = minHeap.poll();
minHeap.offer(maxHeap.poll());
maxHeap.offer(temp);
}
}
bw.append(maxHeap.peek().toString() + "\n");
}
bw.flush();
}
}
이번 문제는 PriorityQueue를 사용한 문제입니다.
PriorityQueue를 이용해서 maxHeap과 minHeap을 사용합니다.
우선순위 조건을 위해 Compartor인터페이스의 메소드를 오버라이딩합니다.
두 개의 PriorityQueue의 크기가 같은 경우 maxHeap에 입력된 값을 추가합니다.
입력한 값이 minHeap의 최솟값보다 크다면 둘의 순서를 바꿉니다.
두 개의 크기가 다른 경우 minHeap에 입력된 값을 추가합니다.
입력한 값이 maxHeap의 최댓값보다 작다면 둘의 순서를 바꿉니다.
maxHeap의 peek 값이 중간 값이 되게 됩니다.
PriorityQueue<Integer> minHeap;
minHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
PriorityQueue<Integer> maxHeap;
maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
기존에 작성했던 코드는 이렇게 오버라이드를 했으나,
람다식을 활용해서 2줄로 줄였습니다.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);