[알고스팟] 변화하는 중간값 :: 늦깎이 IT

[알고스팟 RUNNINGMEDIAN URL]

[참고할만한 알고리즘 이론]

2019/02/16 - [알고리즘 이론] - 우선순위 큐와 힙

2019/02/16 - [알고리즘 이론] - [정렬] 힙 정렬

이 문제를 풀기 위해서 다음과 같은 조건을 수립합니다.

1) 입력받는 데이터들을 두 개의 힙으로 나누되 하나는 최소힙, 나머지 하나는 최대힙으로 구성한다.

2) 최대힙의 크기는 최소힙과 같거나 1만큼 크다.

3) 최대힙의 루트는 최소힙의 루트보다 작거나 같다.

예를 들어, 3, 1, 5, 4, 2의 순서로 데이터가 입력된다고 가정합니다.

1. 데이터 3이 입력되었을 때

1) maxHeap과 minHeap 크기가 같으므로 maxHeap에 저장합니다.

2. 데이터 1이 입력되었을 때

1) maxHeap의 크기와 minHeap크기가 다르므로 minHeap에 저장합니다.

2) maxHeap의 루트 데이터가 minHeap의 루트 데이터보다 크므로 두 데이터(1과 3)을 바꿔줍니다.

3. 1과 2를 반복합니다.

4. 모든 데이터를 위의 조건에 따라 힙에 저장한 뒤 maxHeap에 저장된 데이터가 중간 값입니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static int tCase, N, a, b;
 
    public static void main(String[] args) throws Exception {
 
        tCase = Integer.parseInt(br.readLine());
 
        for (int t = 0; t < tCase; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            System.out.println(runningMedian(N, a, b));
        }
    }
 
    public static Long runningMedian(int N, int a, int b) {
 
        Comparator<Long> maxComp = new Comparator<Long>() {
 
            @Override
            public int compare(Long o1, Long o2) {
                if (o1 > o2)
                    return -1;
                else
                    return 1;
            }
        };
        Comparator<Long> minComp = new Comparator<Long>() {
 
            @Override
            public int compare(Long o1, Long o2) {
                if (o1 > o2)
                    return 1;
                else
                    return -1;
            }
        };
        PriorityQueue<Long> maxHeap = new PriorityQueue<>(maxComp);
        PriorityQueue<Long> minHeap = new PriorityQueue<>(minComp);
 
        long seed = 1983;
        Long result = 0L;
        for (int i = 0; i < N; i++) {
            if (maxHeap.size() == minHeap.size())
                maxHeap.offer(seed);
            else
                minHeap.offer(seed);
 
            if (!minHeap.isEmpty() && !maxHeap.isEmpty() && minHeap.element() < maxHeap.element()) {
                Long maxElement = maxHeap.poll();
                Long minElement = minHeap.poll();
 
                maxHeap.offer(minElement);
                minHeap.offer(maxElement);
            }
            seed = (seed * (long) a + b) % 20090711;
            result = (result + maxHeap.element()) % 20090711;
        }
        return result;
    }
}