[BaekJoon] 1655 가운데를 말해요 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/1655

2.  문제

요약

• 백준이가 정수를 하나씩 외칠 때마다 동생은 지금까지 백준이가 말한 수 중 중간값을 말해야 합니다.
• 만약, 백준이가 외친 수의 개수가 짝수라면 중간에 있는 두 수 중에서 작은 수를 말해야 합니다.
• 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 자연수인 백준이가 외치는 정수의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에 -10,000보다 크거나 같고 10,000보다 작거나 같은 백준이가 외치는 정수들이 주어집니다.
• 출력: N개의 줄에 백준이의 동생이 말해야 하는 수를 한 줄씩 순서대로 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static void input() {
        Reader scanner = new Reader();
        int N = scanner.nextInt();
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for(int idx = 0; idx < N; idx++) {
            if(maxHeap.size() == 0) maxHeap.offer(scanner.nextInt());
            else if(maxHeap.size() == minHeap.size()) maxHeap.offer(scanner.nextInt());
            else minHeap.offer(scanner.nextInt());

            if(maxHeap.size() != 0 && minHeap.size() != 0)
                solution(minHeap, maxHeap);
            else
                sb.append(maxHeap.peek()).append('\n');
        }
    }

    static void solution(PriorityQueue<Integer> minHeap, PriorityQueue<Integer> maxHeap) {
        if(minHeap.peek() < maxHeap.peek()) {
            int maxCentral = maxHeap.poll(), minCentral = minHeap.poll();
            minHeap.offer(maxCentral);
            maxHeap.offer(minCentral);
        }

        sb.append(maxHeap.peek()).append('\n');
    }

    public static void main(String[] args) {
        input();
        System.out.println(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 최대힙과 최소힙을 이용하여 문제를 해결합니다.
• 최대힙과 최소힙을 생성하고 최대힙과 최소힙에 알맞게 주어진 수들을 넣습니다.
  • 만약 최대힙에 아무것도 들어가있지 않다면 최대힙에 수를 넣습니다.
  • 만약 최대힙과 최소힙에 들어있는 수의 수가 같다면 최대힙에 수를 넣습니다.
  • 위 두 경우 모두 아니라면 최소힙에 수를 넣습니다.
• 현재까지 주어진 수들에서 중간값을 찾습니다.
  • 만약 최대힙, 최소힙 모두 수가 하나라도 들어가있다면
    • 최대힙에서의 최댓값과 최소힙에서의 최솟값을 확인합니다.
    • 만약 최대힙에서의 최댓값이 최소힙에서의 최솟값보다 크다면 두 수를 각 힙에서 빼고 각각을 반대 힙에 넣어줍니다.
    • 이후 최대힙에서의 최댓값이 중간값이 됩니다.
  • 그렇지 않다면
    • 최대힙에서의 최댓값이 중간값이 됩니다.
      
      
• 위 작업은 최대힙에는 중간값보다 작거나 같은 수를, 최소힙에는 중간값보다 큰 수를 넣으려는 작업입니다.
  • 처음에 최대힙에 먼저 수를 넣고 두 번째에서는 최대힙에 수를 넣는 두 가지 조건에 모두 포함이 되지 않기 때문에 최소힙에 수를 넣습니다.
  • 만약 여기서 최대힙에 최소힙보다 더 큰 수가 들어가게 된다면 이후 중간값을 찾는 과정에서 최대힙의 값이 최소힙으로, 최소힙의 값이 최대힙으로 변경되게 됩니다.
  • 이후 과정을 생각해보면 최대힙에 먼저 수를 넣고 중간값을 찾는 과정에서 최소힙에서의 최솟값보다 최대힙에 넣은 값이 크다면 최대힙에 넣은 값이 최소힙으로, 최소힙의 최솟값이 최대힙으로 교환되게 됩니다.
  • 그럼 다시 최대힙의 수의 개수가 최소힙의 수의 개수보다 더 많아졌기 때문에 최소힙에 값을 넣게 되고 마찬가지로 중간값을 찾는 과정을 통해 작은 수가 최대힙으로, 큰 수가 최소힙으로 교환되게 됩니다.
  • 그럼 각 과정에서 최대힙의 수의 개수가 항상 최소힙의 수의 개수보다 1 크거나 같게 되고 최대힙의 수들이 최소힙의 수들보다 더 작은 수가 되게 됩니다.
  • 이에 따라 최대힙에서의 최댓값을 뽑아내면 그 값이 중간값이 되게 됩니다. 만약 주어진 수의 개수가 짝수개라면 최대힙에서의 최댓값이 중간값 중 작은 값, 최소힙에서의 최솟값이 중간값 중 큰 값이 되게 됩니다.
• 만약 중간값 중 큰 값을 찾고 싶다면 최소힙과 최대힙의 수를 교환하는 과정은 똑같이 가져가되, 최소힙에 먼저 수를 넣고 최소힙에서의 최솟값을 뽑아내면 중간값 중 큰 값을 찾을 수 있을 것입니다.