BOJ 1655 - 가운데를 말해요

1655번: 가운데를 말해요

 

정수가 하나씩 주어졌을 때 지금까지 언급된 수 중에서 중간값을 말해야 한다.

1 → 1

5 → 1, 5 → 1

2 → 1, 5, 2 → 1, 2, 5 → 2

10 → 1, 2, 5, 10 → 2

-99 → 1, 2, 5, 10, -99 → -99, 1, 2, 5, 10 → 2

7 → -99, 1, 2, 5, 10, 7 → -99, 1, 2, 5, 7, 10 → 2

5 → -99, 1, 2, 5, 7, 10, 5 → -99, 1, 2, 5, 5, 7, 10 → 5

 

리스트에 숫자를 추가해 가며 정렬하고 중간값을 출력하면 된다.

그렇지만 숫자가 추가될 때마다 정렬하고 중간값을 찾으면 시간초과가 발생할 것이다.

중간이라는 의미는 중간 숫자보다 작은 것과 큰 것으로 나눌 수 있다.

1. 첫 입력이 mid값이다.
2. mid를 기준으로 두 그룹으로 나누기 위해 왼쪽 그룹 최대힙과 오른쪽 그룹 최소힙을 설정한다.
3. 다음 입력 값이 mid보다 작으면 왼쪽 그룹, 크다면 오른쪽 그룹으로 간다.
4. 두 그룹간의 크기 비교를 통해 중간값 변경 작업을 수행한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static FastReader scan = new FastReader();
    static int N;

    public static void main(String[] args) {
        N = scan.nextInt();
        List<Integer> result = new ArrayList<>();
        int mid = scan.nextInt();
        result.add(mid);
        PriorityQueue<Integer> left = new PriorityQueue<>((a,b) -> Integer.compare(b, a)); // 최대
        PriorityQueue<Integer> right = new PriorityQueue<>();

        for (int i = 1; i < N; i++) {
            int num = scan.nextInt();
            if (mid < num) {
                right.add(num);
            } else {
                left.add(num);
            }

            if (right.size() - left.size() > 1) {
                left.add(mid);
                mid = right.poll();
            } else if (left.size() - right.size() >= 1) {
                right.add(mid);
                mid = left.poll();
            }
            result.add(mid);
        }

        for (int num : result) {
            System.out.println(num);
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}