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

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

1655번: 가운데를 말해요

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

 

핵심

단순하게 풀려고 하면 시간복잡도에 의해 실패하게 된다.

따라서 우선순위 큐를 활용하여 풀어야 한다.

작은 값, 큰 값을 우선순위로 갖는 큐를 2개 만든다.

이후 minQ, maxQ라고 한다면, 

아래와 같은 로직으로 작동하게 된다.

1. 최대/최소 우선순위 큐의 크기가 같다면 최대 큐에 숫자를 입력해 준다. 같지 않다면 최소 큐에 숫자를 입력해 준다.
2. 최대/최소 우선순위 큐가 비어있지 않고, 최대 큐의 루트값이 더 크다면 최소 큐의 루트값과 자리를 바꾸어 준다.
3. 최대 우선순위 큐의 루트값을 출력한다.

즉 maxQ의 peek값을 중앙값으로 유지하는 것이다.

코드를 통해 확인해 보자.

 

 

정답 코드

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));
        PriorityQueue<Integer> minQ = new PriorityQueue<>();
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Comparator.reverseOrder());
        StringBuilder sb = new StringBuilder();

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

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

            if (maxQ.size() == minQ.size()) maxQ.offer(value);
            else minQ.offer(value);

            if (!minQ.isEmpty() && !maxQ.isEmpty()){
                if (maxQ.peek() > minQ.peek()){
                    Integer poll = minQ.poll();
                    minQ.offer(maxQ.poll());
                    maxQ.offer(poll);
                }
            }
            sb.append(maxQ.peek()).append("\n");
        }
        System.out.println(sb);
    }
}

해설

앞서 말한 대로 큐에 넣을 때 3가지 로직을 통해 수행된다.

큐의 사이즈가 같다면 maxQ에 값을 넣고, 다르면 minQ에 넣는다.

이후 maxQ의 peek 값과 minQ의 peek값을 비교하여 maxQ가 더 크다면 둘을 교환하게 된다.

 

 

배운 점

위와 같은 논리적 사고가 있다면 쉽게 풀 수 있다고 생각한다.

하지만 위와 같은 사고를 하는 것이 분명 쉽지 않고, 많은 문제를 풀면서 성장하는 것이 답이라 생각한다.

시간복잡도를 중요하게 생각할 수 록 어려운 것 같다.