[백준] 1655번 가운데를 말해요 (JAVA)

문제

- 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 말한 수 중에서 중간값을 말해야 함

- 그동안 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 함

- 백준이의 동생이 말해야 하는 수를 순서대로 출력

 

해결방법

처음에는 리스트에 백준이가 정수를 외칠 때마다 넣어주면서 정렬을 하고, 가운데 인덱스를 구해 해당 인덱스의 숫자를 출력하는 방식으로 문제를 해결하려 했었는데 시간초과가 났다. 

구글링을 통해 우선순위 큐를 두개를 써서 숫자를 계속 정렬해가면서 값을 빠르게 찾아나갈 수 있는 방법을 찾았다. 우선순위 큐 두개를 활용한 방법으로 한개씩 번갈아가면서 숫자를 넣어주면서 자동 정렬될 수 있도록 하였다. 차례로 각각에 번갈아 숫자를 넣어주었지만, 순서대로 큐에 넣었던 것이기 때문에 작은 숫자들을 저장하고 있는 큐의 가장 큰 값이 큰 숫자들을 저장하고 있는 큐의 가장 작은 값보다 큰 경우가 생길 수도 있다.

예를 들어 [작은 큐](1, 2) [큰 큐](3, 4)가 들어있는 상태에서 5라는 숫자가 들어왔을 때, 순서대로 큐에 입력되는 거라면 작은 큐에 5가 들어가야 한다. 하지만 그렇게 되면 정렬이 제대로 이루어지지 않기 때문에 작은 큐의 가장 큰 값과 큰 큐의 가장 작은 값을 비교하여 두 개를 swap 해주는 방식으로 코드를 작성한 것이다. 그렇게 되면 [작은 큐](1, 2, 5) [큰 큐](3, 4)였던 것을 [작은 큐](1, 2, 3) [큰 큐](4, 5)로 바꿀 수 있다. 

그리고 작은 큐를 정렬 기준을 내림차순으로 정렬해 두면 peek()함수를 통해 작은 큐 내의 가장 큰 값을 확인할 수 있다. 따라서, 중간 값을 바로 확인할 수 있다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

	// 작은 수들 저장 큐(내림차순 정렬 - 중간값을 peek() 함수로 바로 확인하기 위해)
        PriorityQueue<Integer> min = new PriorityQueue<>(((o1, o2) -> o2 - o1));
        // 큰 수들 저장 큐
        PriorityQueue<Integer> max = new PriorityQueue<>();

        for(int i = 0; i<N; i++) {
            int num = Integer.parseInt(br.readLine());
			
            // 한 큐씩 번갈아가면서 숫자 저장
            // 각각 같은 개수의 숫자를 가지고 있다면 min 큐에 저장
            if(min.size() == max.size()) min.add(num);
            // 다른 개수라면 max 큐에 저장
            else max.add(num);
			
            // 숫자를 넣고 나서 숫자 정렬을 올바르게 하기 위해
            if(!min.isEmpty() && !max.isEmpty()) {
            	// min 큐의 가장 큰 값과 max 큐의 가장 작은 값을 비교
                // 만약 min 큐에 더 큰 값을 가지고 있다면 swap
                if(max.peek() < min.peek()) {
                    int tmp = max.poll();
                    max.add(min.poll());
                    min.add(tmp);
                }
            }
			
            // 중간 값을 차례로 출력하기 위해 StringBuilder에 값 저장
            sb.append(min.peek()).append("\n");
        }
        System.out.println(sb);
    }
}