[백준] G2 1655 가운데를 말해요 (java)

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

1655번: 가운데를 말해요

 

풀이

 

1) PriorityQueue 를 2개 사용한다. (최대힙, 최소힙)

2) 입력받은 숫자를 하나씩 넣는다.
  2-1) 맨 처음 maxHeap이 비어있을경우 maxHeap에 우선적으로 넣는다.
  2-2) 들어올 숫자가 maxHeap의 peek 값보다 작으면 무조건 maxHeap에 넣는다.
         만약 maxHeap의 크기가 minHeap의 크기 + 2 보다 커지면 maxHeap의 peek를 minHeap에 보낸다.
  2-4) 들어올 숫자가 maxHeap의 peek 값보다 크면 minHeap에 넣는다.
         만약 minHeap의 크기가 maxHeap의 크기보다 커지면 minHeap의 peek를 maxHeap에 보낸다.

3) 매 루프마다 maxHeap의 peek값을 담아 출력한다.

 

 

주의사항

 

1) List 하나만 써서 매번 정렬하여 인덱스로 찾으면 시간초과난다.

 

package com.baekJoon;

import java.io.*;
import java.util.Collections;
import java.util.PriorityQueue;

public class BJ_G2_1655_가운데를말해요 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        int N = Integer.parseInt(input.readLine());

        for(int i=0; i<N; i++){
            int num = Integer.parseInt(input.readLine());
            if(maxHeap.isEmpty()) maxHeap.add(num);
            else if (maxHeap.peek() > num) {
                maxHeap.add(num);
                if(maxHeap.size() == minHeap.size()+2){
                    minHeap.add(maxHeap.poll());
                }
            }else{
                minHeap.add(num);
                if(maxHeap.size() < minHeap.size()){
                    maxHeap.add(minHeap.poll());
                }
            }
            output.append(maxHeap.peek()+"\n");
        }
        output.close();
    }

    static String src =
            "9\n" +
            "1\n" +
            "5\n" +
            "2\n" +
            "10\n" +
            "-99\n" +
            "7\n" +
            "11\n" +
            "12\n" +
            "5";
}

 

 

 

후기

 

 사실 아무리 머리 싸매도 시간초과를 해결할 방법이 떠오르지 않아 솔루션을 찾아봤다. 

이렇게 단순 해결은 간단하지만 시간초과를 고민해야하는 문제에 다소 약한것 같다.