[알고리즘] 백준 > #2696. 중앙값 구하기

문제링크

백준 #2696. 중앙값 구하기

풀이방법

음 보자마자 풀이방법이 떠오른 문제는 아니다. 처음엔 중앙값의 의미를 생각해서 두개씩 추가할때 그 케이스를 나눠서 생각해봤다. 추가되는 두 값을 valueA, valueB라고 하겠다.

1. valueA < mid && valueB < mid
   👉 n(mid보다 작은 수의 개수), 1(mid), n(mid보다 큰 수의 개수) 이 상태에서 n + 2, 1, n가 되기 때문에 n + 1, 1, n + 1 이렇게 재분배 해 mid 값을 찾아야 했다. 따라서, mid보다 작은 수의 그룹에서 가장 큰 수가 mid가 된다.
2. valueA > mid && valueB > mid
   👉 n(mid보다 작은 수의 개수), 1(mid), n(mid보다 큰 수의 개수) 이 상태에서 n, 1, n + 2가 되기 때문에 n + 1, 1, n + 1 이렇게 재분배 해 mid 값을 찾아야 했다. 따라서, mid보다 큰 수의 그룹에서 가장 작은 수가 mid가 된다.
3. else
   👉 n + 1, 1, n + 1이기 때문에 재분배가 필요없다!

이런 아이디어까지 오니까 우선순위큐를 사용해야겠다고 생각했다. 다만, mid보다 작은 그룹은 내림차순, mid보다 큰 그룹은 오름차순을 우선순위로 가져야 한다.

코드

class Solution2696 {
    int m;
    LinkedList<Integer> list;

    Solution2696(int m, LinkedList<Integer> list) {
        this.m = m;
        this.list = list;
    }

    LinkedList<Integer> getMidValues() {
        LinkedList<Integer> midValues = new LinkedList<>();

        PriorityQueue<Integer> preQ = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> postQ = new PriorityQueue<>();
        int mid = list.get(0);
        midValues.add(mid);

        int i = 1;
        while (i < m) {
            int valueA = list.get(i++);
            int valueB = list.get(i++);

            if (valueA < mid) preQ.offer(valueA);
            else postQ.offer(valueA);

            if (valueB < mid) preQ.offer(valueB);
            else postQ.offer(valueB);

            if ((valueA < mid) && (valueB < mid)) {
                postQ.offer(mid);
                mid = preQ.poll();
            } else if ((valueA > mid) && (valueB > mid)) {
                preQ.offer(mid);
                mid = postQ.poll();
            }

            midValues.add(mid);
        }

        return midValues;
    }
}