[백준 1655] 가운데를 말해요 - Java 문제풀이

오늘의 1일 1골드 문제는 다음 문제이다.

 

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

1655번: 가운데를 말해요

 

문제

문제

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

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

입력

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

해설

이 문제는 방법을 알고 있으면 쉽다.

가운데를 말하는 법은 가운데 수를 기준으로 우선순위 큐를 2개를 두고 푸는 것이다.

 

1. minQueue는 가운데수보다 작은 수들의 큐이며 숫자가 큰 것부터 나오게 된다.

2. maxQueue는 가운데수보다 큰 수들의 큐이며 숫자가 작은 것부터 나오게 된다.

맨 처음 수는 1이니 첫 가운데수를 1로 초기화해준다.

 

5라는 수가 다음으로 말해지면 가운데수인 1과 비교하여 작다면 minQueue, 크다면 maxQueue 에 넣어준다.

이 때, maxQueue-minQueue가 0 또는 1이 될 시가 아니라면 가운데수를 바꾸어주고 그 외의 상황에서는 초기화하지 않는다.

다음으로는 2가 들어왔다. 이 경우가 위에서 얘기한 maxQueue-minQueue 가 0이나 1이 아닌 경우이다. 이 경우에는 maxQueue의 사이즈가 더 크기 때문에 maxQueue에서 숫자를 빼면 된다.

방법은 간단한데, 일단 minQueue에 1을 넣고, maxQueue에서 가장 작은 수를 꺼내 가운데수로 설정해주면 된다.

반대로 다음으로 -10이 들어왔다고 생각해보자.

문제에서 짝수개라면 가운데의 2개의 수 중 작은 수를 말하라고 했다. 따라서 minQueue의 사이즈가 maxQueue의 사이즈보다 커질 수 없다. 이러한 경우에는 maxQueue에 가운데 수를 넣고, minQueue에서 가장 큰 수를 꺼내 가운데수로 설정해주면 된다.

다음은 코드 전문이다.

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

public class BOJ_1655 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        // 작은 수가 들어있는 큐. 큰 수부터 가져온다.
        PriorityQueue<Integer> minQueue = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
        // 큰 수가 들어있는 큐. 작은 수부터 가져온다.
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>();
        int mid = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        sb.append(mid+"\n");
        for(int t=2;t<=N;t++) {
            int num = Integer.parseInt(br.readLine());
            // 일단 숫자 넣기
            if (num < mid) {
                minQueue.add(num);
            } else {
                maxQueue.add(num);
            }
            // 만약 maxQueue의 사이즈가 minQueue와 같거나 1 크지 않는다면 가운데수를 재설정해준다.
            if (!(minQueue.size() == maxQueue.size() || minQueue.size() == maxQueue.size() - 1)){
                if (minQueue.size() < maxQueue.size()) {
                    minQueue.add(mid);
                    mid = maxQueue.poll();
                } else {
                    maxQueue.add(mid);
                    mid = minQueue.poll();
                }
            }
            sb.append(mid+"\n");
        }
        System.out.println(sb.toString());
    }
}

 

 

---

 

해당 문제를 푸는 데에는 총 15분이 소요되었다. 이 문제와 비슷한 문제를 SW 역량테스트 B형을 풀 때에 만났어서인지 방법에 대해 인지하고 풀어 시간이 얼마 걸리지 않은 듯 하다. 그리고 또 메모리랑 코드길이가 100으로 나누어떨어지는거 너무 좋다..ㅎㅎ

오랜만에 티어가 높은 문제를 풀어봤는데 확실히 티어가 높은 문제는 풀이 방법만 알고 있다면 얼마 안걸리는 듯 하다.(약간 어려워서 높다기보단 방법이 있어서 높은 느낌..) 더 공부해야겠다..ㅎㅎ