1655번 - 가운데를 말해요

2024-07-22

#JAVA#백준

문제 풀이 시간 : 2시간

문제 요약

•
N 개의 수를 외친다.

•
정수를 하나씩 외칠때마다 지금까지 말한 수 중 중간값을 말해야한다.

•
외친 수가 짝수 개라면 중간에 있는 두 수 중 작은 수를 말한다.

문제 풀이

처음에는 그냥 막무가내로 정렬을 해서 가운데 출력하면 되는거 아닌가?

했는데

시간 제한이 0.1초여서 불가능하다는걸 깨달았다.

그래서 뭔가 우선순위큐를 사용해야겠다고 생각했는데, 우선순위큐를 사용하면 가운데를 어떻게 출력할까? 라고 고민을 해보았다.

그래서 생각했던게 우선순위큐를 하나 만들어서 중간 값을 찾는 것이다.

Java

for (int i = 0; i < N; i++) {
            pq.add(Integer.parseInt(br.readLine()));

            List<Integer> temp = new ArrayList<>();
            int mid = pq.size()/2;
            int size = pq.size();
            for (int j = 0; j < mid; j++) {
                temp.add(pq.poll());
            }
            if(size%2!=0){
                System.out.println(pq.peek());
            }
            else{
                System.out.println(Math.min(pq.peek(), temp.get(temp.size()-1)));
            }
            pq.addAll(temp);
        }

매번 이런 식으로 우선순위 큐에서 절반만큼을 리스트에 빼내어 가운데 수를 출력하고 다시 우선순위큐에 집어넣는 방식이다.

당연하게도 시간초과가 났다.

너무 비효율적인 방식인 것 같긴하다.

그렇게 여러가지 방법을 시도해보았지만 도저히 풀 수 없어서

똑똑하신 구글의 힘을 빌렸다.

이 문제는 두개의 우선순위 큐를 사용해야하는 문제였다.

minHeap, maxHeap 두가지 우선순위 큐를 사용하여 가운데 수를 빠르게 찾는 것인데,

먼저, 두 개의 우선순위 큐의 크기가 같다면 maxHeap에 값을 추가한다.

하지만 입력된 값이 minHeap 의 top 보다 크다면 입력된 값과 해당 값을 스왑한다.

두 개의 우선순위 큐의 크기가 다르다면 minHeap에 값을 추가한다.

하지만 입력된 값이 maxHeap 의 top 보다 작다면 입력된 값과 해당 값을 스왑한다.

그리고 매번 maxHeap의 top이 가운데 값이 되게 된다.

그렇다면 왜 위와 같이 동작할까?

쉽게 생각하면 maxHeap에는 가운데 수를 기준으로 작은 수들, minHeap에는 가운데 수를 기준으로 큰 수들이 들어간다고 생각하면 된다.

예를 들어,

10 8 5 3 5 -1 의 순서로 입력이 들어온다고 생각하자.

•
10 입력

maxHeap	minHeap
10

•
8 입력

위와 같이 입력이 들어오지만, 원래 두개의 우선순위 큐의 크기가 다른 상태에서

입력된 값이 maxHeap의 top 보다 작기 때문에 두 값을 스왑한다.

•
5 입력

5 8

•
3 입력

5 8

3 10

입력된 값이 maxHeap의 top인 8보다 작기 때문에 두 값 스왑

3 5

8 10

•
5 입력

3 5 5

8 10

•
-1 입력

3 5 5

-1 8 10

입력된 값이 maxHeap의 top인 5보다 작기 때문에 두 값 스왑

-1 3 5

5 8 10

위와 같이 결국 가운데 수를 기준으로 작은 수들은 maxHeap으로, 큰 수들은 minHeap으로 모이게 되어 결국 가운데수를 출력할 수 있게 된다.

위 내용을 참고하여 코드를 다시 짜본다면 아주 간단하게 풀 수 있다.

정답 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> min = new PriorityQueue<>();
        PriorityQueue<Integer> max = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

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

            if (min.size() == max.size()) {
                if(!min.isEmpty() && min.peek()<input){
                    max.add(min.poll());
                    min.add(input);
                }
                else{
                    max.add(input);
                }
            }
            else{
                if(!max.isEmpty() && max.peek()>input){
                    min.add(max.poll());
                    max.add(input);
                }
                else{
                    min.add(input);
                }
            }
            sb.append(max.peek()).append("\n");
        }
        System.out.println(sb);
        
    }
}