[Baekjoon] 1655: 가운데를 말해요

문제

수가 순차적으로 주어지면 입력된 수 들 중에서 중간값을 계속 출력해나가는 문제이다 -> 짝수개 일 시 더 작은 값 출력

 

풀이

내 풀이

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Q1655 {

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

        // 최대힙, 최소힙 하나씩 생성
        Queue<Integer> left = new PriorityQueue<>(Comparator.comparingInt(c -> -c));
        Queue<Integer> right = new PriorityQueue<>(Comparator.comparingInt(c -> c));

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

        // 최대힙에 초기값 삽입
        int one = Integer.parseInt(br.readLine());
        left.offer(one);
        sb.append(one).append("\n");

        for (int i = 1; i < n; i++) {
            int num = Integer.parseInt(br.readLine());

            int peek = left.peek();

            // 각 값을 초기값과 비교하여 크기에 따라 삽입
            if (num <= peek) {
                left.offer(num);
            } else {
                right.offer(num);
            }

            // 사이즈가 1개 이하 차이날 때 까지 조정
            while (left.size() - right.size() > 1) {
                right.offer(left.poll());
            }

            while (right.size() - left.size() > 0) {
                left.offer(right.poll());
            }

            sb.append(Math.min(left.peek(), right.peek())).append("\n");
        }

        System.out.print(sb);
    }
}

이 문제는 풀이가 오래 걸렸던 것 같다.

필기를 몇시간 하고나서야 중간값을 찾을 방법을 떠올렸다.

큐 2개를 사용하여 하나는 최대 힙, 하나는 최소 힙으로 만든 다음, 두 큐의 사이즈 차이가 최대 1이 될때까지 사이즈를 조정하여 값을 꺼내주는 것이다.

이렇게 하면 금방 풀이가 가능하다. 이 문제는 전에 한 번 풀어본 기억이 있음에도 오랜만에 푸니까 풀이를 떠올리는데 너무 오래걸렸다

 

회고

큐 말고도 이분 탐색으로도 풀이가 가능하다고 한다. 정해는 큐이겠지만, 한 번 이분탐색으로도 풀이해볼 필요가 있을 것 같다.