[우선순위 큐][백준 1655] 가운데를 말해요

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

 

 

문제

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

 

핵심

• 우선순위 큐는 항상 root를 가장 높은 우선순위를 유지하도록 하는 특징이 있다.

 

풀이

• 입력 값이 주어지는 과정 중에 가운데 값을 출력해야 한다. 
• 2개의 우선순위 큐를 사용하면 입력값이 주어지는 과정에서 빠르게 중간 값을 출력할 수 있다. 
• max heap 과 min heap 은 root에 가장 높은 우선순위 값을 유지한다. 
• 두 heap의 size를 N/2로 유지하면 N 개 입력을 받는 동안 가운데 값을 찾을 수 있다. 

 

 

package priorityqueue;

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

public class Baek1655 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        
        // max heap 을 reverse order로 유지하도록 설정
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> min = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int val = Integer.parseInt(br.readLine());
            
            // N이 짝수개일 떄 두 수 중에서 작은 값을 선택해야 한다. 
            // max heap 크기를 min heap 보다 같을 경우 max heap의 root가 작은 값이 된다.
            if (max.size() <= min.size()) {
                max.add(val);

                if (!min.isEmpty() && max.peek() > min.peek()) {
                    min.add(max.poll());
                    max.add(min.poll());
                }
            } else {
                min.add(val);

                if (max.peek() > min.peek()) {
                    min.add(max.poll());
                    max.add(min.poll());
                }
            }

            sb.append(max.peek()).append("\n");
        }
        System.out.println(sb.toString());
    }
}

 

 

 

 

틀린 풀이 - 메모리 초과 

 

1개의 우선순위 큐(pq)와 리스트(list)로 풀이하려고 했다. 

 

잘못된 과정

• 입력 매 순간 pq에 추가하고 답을 출력할 때 pq 크기가 N/2 까지 poll하면서 list에 추가 
• 중간 값 출력
• list에서 다시 pq로 값 추가 

list에서 poll하기 때문에 메모리 문제가 없을꺼라 생각했다. 

하지만 poll해도 남은 메모리 공간은 아직 남아있기에 1+2+... N 크기의 메모리가 사용되어 메모리 초과가 되었을 것이다. 

(전체 메모리 입장에서 GC 대상이 될정도로 큰 차지는 안할 것이기에 따로 메모리가 정리되지 않았을 것으로 봄)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        Queue<Integer> list = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            int val = Integer.parseInt(br.readLine());
            pq.add(val);

            int size = pq.size();
            int pollval = 0;

            while(size/2 != pq.size()) {
                pollval = pq.poll();
                list.add(pollval);
            }

            System.out.println(pollval);
            while (!list.isEmpty()) {
                pq.add(list.poll());
            }
        }
        
    }
}