문제
어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.
예를 들어, 수열이 1, 5, 4, 3, 2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.
입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다.
출력
각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.
예제 입력 1
3
9
1 2 3 4 5 6 7 8 9
9
9 8 7 6 5 4 3 2 1
23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56
예제 출력 1
5
1 2 3 4 5
5
9 8 7 6 5
12
23 23 22 22 13 3 5 5 3 -3
-7 -3
풀이
이번거는 PriorityQueue를 이용해서 푸는 문제인줄 몰랐다. 그저 리스트로서 하나씩 접근하면 되는줄 알았지만 그렇게 쉽게 문제를 만들리가 없다.. ㅠㅠ 이번 문제 또한 최근에 푼 문제들과 비슷하게 Priorityqueue를 두개를 만들어 minqueue와 maxQueue를 이용하여 푸는 문제였다.
먼저 while문을 돌리면서 M+1/2 의 값을 stringtokenizer에 넣어둔 상태로 두개의 Priorityqueue를 만든다. 최소 힙은 내림차순, 최대 힙은 오름차순으로 정렬해서 중앙값을 접근할 수 있도록 해준다. 그런 다음 만약 두 힙의 사이즈가 같다는 것은 이제 홀수번째의 수가 들어가는 순간을 의미하므로 최대힙에 저장을 해준다. 그리고 두 힙의 사이즈가 다른 경우는 짝수번재가 들어가는 타이밍 이므로 최소힙에 저장을 해준다. 그런 다음 매번 최소 힙의 최대값과 최대 힙의 최솟값을 비교해서 최소 힙의 최댓값 > 최대 힙의 최솟값일때 그 둘을 바꿔준다. 그리고 홀수번째의 수를 매번 출력해야하므로 i가 2로 나누어떨어질때 중앙값을 출력해준다!
사실 여기서 궁금한점은
왜 홀수는 max , 짝수는 min queue에 넣는 것!
그리고 하나하나 알고리즘을 타고 들어가보면 왜 매번 교환해야하는지 이해는 하지만 처음에 이를 어떻게 생각하는지 등이 궁금했습니다. ㅠㅠ
GPT 답변
최대 힙은 내림차순으로 정렬되어 있으므로, 최대 힙의 루트에 있는 값이 중앙값이 됩니다. 최소 힙은 오름차순으로 정렬되어 있지만, 중앙값을 구할 때는 최대 힙의 최솟값을 사용합니다.
따라서, 홀수번째 수는 최대 힙에 넣고, 짝수번째 수는 최소 힙에 넣어야 합니다. 이렇게 하면 최대 힙의 루트에 있는 값이 항상 중앙값이 되기 때문에, 중앙값을 쉽게 접근할 수 있습니다.
만약 반대로 홀수를 최소 힙에, 짝수를 최대 힙에 넣는다면, 중앙값을 구할 때 최소 힙의 최댓값을 사용해야 합니다. 이는 최소 힙의 루트에 있는 값이 중앙값이 되는 것을 의미하며, 구현 방식이 달라지게 됩니다.
코드
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(st.nextToken());
while(T-->0){
st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
sb.append((M+1)/2);
sb.append("\n");
PriorityQueue<Integer> minPQ = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> maxPQ = new PriorityQueue<>();
int cnt = 0;
for(int i=0;i<M;i++){
if(i%10==0) st = new StringTokenizer(br.readLine());
int var = Integer.parseInt(st.nextToken());
if(minPQ.size() == maxPQ.size()) maxPQ.add(var);
else minPQ.add(var);
if(!minPQ.isEmpty() && !maxPQ.isEmpty()){
if(minPQ.peek() > maxPQ.peek()){
int tmp = maxPQ.poll();
maxPQ.add(minPQ.poll());
minPQ.add(tmp);
}
}
if(i%2==0){
sb.append(maxPQ.peek());
sb.append(" ");
cnt++;
if(cnt%10==0) sb.append("\n");
}
}
sb.append("\n");
}
System.out.println(sb);
}
}