[백준 - Java] 1655번 : 가운데를 말해요

문제

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

설명

최대 힙과 최소 힙을 사용해 문제를 풀었다.

1. 우선순위 큐를 사용해 최소 힙, 최대 힙 두 개를 만든다.
2. 최소 힙, 최대 힙에 번갈아 가면서 하나씩 숫자를 추가해 준다. -> 두 개의 힙의 크기가 같을 경우 최대 힙에 숫자를 추가하고, 다를 경우 최소 힙에 숫자를 추가한다.
3. 최대 힙의 최대값이 최소 힙의 최소값보다 클 경우 각 힙의 top 값을 바꿔줘야 한다.
4. 최대 힙의 최대값이 최소 힙의 최소값보다 작은 게 유지되어야지만 최대 힙의 최대값이 가운데 숫자가 된다.

주의할 점
System.out.println를 사용할 경우 시간 초과가 발생하기 때문에 BufferedWriter를 사용해야 한다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
		
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 오름차순으로 정렬
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); // 내림차순으로 정렬
		
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
			
            // 최소 힙과 최대 힙에 번갈아 가면서 숫자를 넣어줌
            // 최소 힙과 최대 힙의 크기가 같을 경우 최대 힙에 숫자를 넣고, 아닐 경우 최소 힙에 넣음
            if (minHeap.size() == maxHeap.size()) {
                maxHeap.add(num);
            }
            else {
                minHeap.add(num);
            }
			
            if (!minHeap.isEmpty() && !maxHeap.isEmpty()) {
                // 최대힙의 최대값이 최소힙의 최소값보다 큰 경우
                if (maxHeap.peek() > minHeap.peek()) {
                    // 두 숫자의 위치를 바꿔줌
                    int tmp = minHeap.poll();
					
                    minHeap.add(maxHeap.poll());
                    maxHeap.add(tmp);
                }
            }
			
            // maxHeap의 최대값이 가운데 숫자가 됨
            bw.write(maxHeap.peek() + "\n");
        }
		
        bw.flush();
        bw.close();
    }

}

GITHUB

https://github.com/MinchaeKwon/BOJ/blob/master/BOJ%231655/src/Main.java