[SWEA] 3000. 중간값 구하기

[3000. 중간값 구하기]

문제

---

7개의 숫자 중 중간값은 정렬했을 때 4개와 3개로 나뉠 수 있다. 그러면 maxHeap 에 작은 값부터 4개, minHeap에 큰 값부터 3개를 넣는다면 maxHeap 의 루트노드가 중간값이 될 것이다.

위의 생각을 바탕으로 maxHeap, minHeap 을 통해 중간값을 확인할 수 있다.

이때 (maxHeap 의 가장 작은 값 < minHeap 의 가장 큰 값) 을 계속해서 유지해야한다. 따라서 숫자를 minHeap에 넣어 루트 노드값을 비교 한 후 maxHeap에 넣어 루트 노드값을 비교해야한다.

포인트

---

코드

---

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.io.FileInputStream;

public class Solution {
    static StringBuilder result = new StringBuilder();

    public static void main(String args[]) throws Exception {

        try (Scanner sc = new Scanner(System.in)) {
            int T;
            T = sc.nextInt();

            int N;
            //////////////////////////
            int temp, sum;
            PriorityQueue<Integer> minHeap = new PriorityQueue<>();
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
            for (int test_case = 1; test_case <= T; test_case++) {
                result.append("#" + test_case + " ");
                N = sc.nextInt();
                /////////////////////////////
                sum = 0;
                maxHeap.add(sc.nextInt());

                for (int i = 0; i < N; i++) {
                    minHeap.add(sc.nextInt());
                    if (minHeap.peek() < maxHeap.peek()) {
                        temp = minHeap.poll();
                        minHeap.add(maxHeap.poll());
                        maxHeap.add(temp);
                    }

                    maxHeap.add(sc.nextInt());
                    if (minHeap.peek() < maxHeap.peek()) {
                        temp = minHeap.poll();
                        minHeap.add(maxHeap.poll());
                        maxHeap.add(temp);
                    }
                    sum = (sum + maxHeap.peek()) % 20171109;
                }

                maxHeap.clear();
                minHeap.clear();
                result.append(sum + "\n");
            }
            System.out.println(result);
        }
    }
}