<BOJ> 1655 자바 (가운데를 말해요)

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

Peranakan Museum, Singapore

 

 

우선 문제를 풀기 전 최대힙과 최소힙 자료구조 개념을 알고 가면 좋을 문제이다.

https://true-false.tistory.com/12

 

 

처음 문제를 봤을 땐 간단한 거 치고 티어가 낮지 않아서 조금 의아했다.

그 마음으로 ArrayList를 작성해서 풀었는데 역시나 시간초과가 발생하더라..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;

public class b1655_가운데를말해요 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> arr = new ArrayList<>();

        for (int i = 1; i <= N; i++) {
            int input = Integer.parseInt(br.readLine());
            arr.add(input);
            arr.sort(Comparator.naturalOrder());
            int num;
            if (i % 2 == 0) {
                num = arr.get(arr.size()/2 -1);
            } else {
                num = arr.get(arr.size()/2);
            }
            System.out.println(num);
        }
    }
}

 

 

위 코드를 보면 매번 ArrayList를 정렬하게 되어 정렬의 시간 복잡도인 O(N log N)이 발생하게 되어, 전체 시간 복잡도가 O(N^2 log N)이 된다. 이는 입력의 크기 N이 커질수록 매우 비효율적이다.

 

효율적인 중간값 찾기를 위해서는 최대 힙(Max-Heap)과 최소 힙(Min-Heap)을 사용하여 두 힙을 균형있게 유지하는 것이 좋다.

최대 힙과 최소 힙을 사용하면 O(log N) 시간 복잡도로 중간값을 유지할 수 있다고 한다.

 

풀이 코드

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

public class b1655_가운데를말해요 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(br.readLine());
            if (minHeap.size() >= maxHeap.size()) {
                maxHeap.add(input);    // 중앙값을 효율적으로 구하려면 최대힙에 우선 삽입, 예로 첫번 째 값이 들어오면 해당값이 중앙값
            } else minHeap.add(input);

            if (!minHeap.isEmpty() && !maxHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
                int maxRoot = maxHeap.poll();
                int minRoot = minHeap.poll();
                maxHeap.add(minRoot);
                minHeap.add(maxRoot);
            }
            sb.append(maxHeap.peek()).append("\n");
        }
        System.out.println(sb.toString());
    }
}

 

참고로, StringBuilder를 사용하지 않고 매번 최대힙 루트값을 출력해줘도 시간초과가 발생한다.