[분류]

  • 우선순위 큐

[문제링크]

[요구사항]

  • 한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

[풀이]

  1. 최소힙과 최대힙을 사용한다.

  2. 힙의 사이즈가 동일하면 최대힙에 넣고 아니면 최소힙에 넣는다.

  3. 이 때, 최대힙의 최댓값이 무조건 최소힙의 최소값보다 작아야하므로 그렇지 않으면 swap해준다.

  4. 최대힙의 최댓값을 출력하는 한다.

  5. 이를 반복한다.

[처음에 짠 코드]

//baekjoon_1655_가운데를 말해요

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{
    static int n;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        Arrays.fill(arr, 100001);

        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(br.readLine());
            Arrays.sort(arr);
            sb.append(arr[i/2]+"\n");
        }

        System.out.println(sb.toString());
    }
}



[코드]

//baekjoon_1655_가운데를 말해요

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

public class Main{
    static int n;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2)->o2-o1);
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2)->o1-o2);

        for(int i=0;i<n;i++){
            int num = Integer.parseInt(br.readLine());

            if(maxHeap.size()==minHeap.size()) maxHeap.add(num);
            else minHeap.add(num);
            //우선 사이즈가 다르면 무조건 맞춰줘야하기 때문에 일단 값을 어디든 넣는다.

            if(!maxHeap.isEmpty() && !minHeap.isEmpty()){//한쪽이라도 비어있으면 안된다.
                if(maxHeap.peek()>minHeap.peek()){
                    minHeap.add(maxHeap.poll());
                    maxHeap.add(minHeap.poll());
                }
            }
            sb.append(maxHeap.peek() + "\n");
        }
        System.out.println(sb.toString());
    }
}



[통과여부]

image

[느낀점]

처음에는 단순히 우선순위 큐 하나만으로 구할 수 있어서 쉽다고 생각했는데, 시간초과와 메모리초과의 문제가 있어서 두 개를 사용해서 구현하는게 신박했다.