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

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

소요 시간: 10분
메모리: 36252KB
시간: 380ms

---

🔥 문제

백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

---

🍀 풀이

두 개의 우선순위 큐를 활용하여 문제를 풀었다.

 

하나는 가장 큰 값을 가져오는 우선순위 큐로, 여기에는 백준이가 지금까지 부른 숫자 중 절반에 해당하는 작은 값들을 저장한다. (`small_pq`)

지금까지 부른 숫자가 홀수개인 경우 이곳에 숫자 하나를 더 넣는다.

 

다른 하나는 가장 작은 값을 가져오는 우선순위 큐로, 여기에는 백준이가 지금까지 부른 숫자 중 절반에 해당하는 큰 값들을 저장한다. (`big_pq`)

 

항상 `small_pq`의 사이즈와 `big_pq`사이즈가 같거나, `small_pq`의 사이즈가 `big_pq`사이즈보다 1 커야한다.

입력을 받은 후 `small_pq`의 가장 큰 값이 중간값이 되도록 만들 것이다.

 

7
1
5
2
10
-99
1

 

위와 같은 예시가 주어졌다고 했을 때, 먼저 첫번째 입력은 `small_pq`에 넣고 이를 출력한다.

 

그 다음 입력은 `small_pq`의 가장 큰값과 비교한다. 예시에서는 1보다 큰 5가 입력으로 주어졌다.

`small_pq`보다 입력값이 큰 경우는 `big_pq`에 저장한다.

`small_pq`와 `big_pq`의 사이즈가 같으므로 중간에 있는 수 중 더 작은 `small_pq`의 가장 큰 값을 출력한다.

 

그 다음 입력인 2는 1보다 크므로 `big_pq`에 저장한다.

`small_pq`의 사이즈보다 `big_pq`의 사이즈가 크다. 중간값을 항상 `small_pq`의 제일 큰 값으로 가져오기 위해서 `small_pq`보다 `big_pq`의 사이즈가 큰 경우, `big_pq`의 제일 작은 값을 빼서 `small_pq`에 넣는다.

 

`small_pq`의 사이즈가 `big_pq`의 사이즈보다 1 크므로 중간값인 `small_pq`의 가장 큰 값을 출력한다.

 

그 다음 입력인 10은 2보다 크므로 `big_pq`에 저장한다.

`small_pq`와 `big_pq`의 사이즈가 같으므로 중간에 있는 수 중 더 작은 `small_pq`의 가장 큰 값을 출력한다.

 

그 다음 입력인 -99은 2보다 작으므로 `small_pq`에 저장한다.

`small_pq`의 사이즈가 `big_pq`의 사이즈보다 1 크므로 중간값인 `small_pq`의 가장 큰 값을 출력한다.

 

 

 

그 다음 입력인 1은 2보다 작으므로 `small_pq`에 저장한다.

`big_pq`의 사이즈를 +1한 것보다 `small_pq`의 사이즈가 크다. 중간값을 항상 `small_pq`의 제일 큰 값으로 가져오기 위해서 `big_pq`의 사이즈+1 보다 `small_pq`의 사이즈가 큰 경우, `small_pq`의 제일 큰 값을 빼서 `big_pq`에 넣는다.

 

`small_pq`의 사이즈가 `big_pq`의 사이즈보다 1 크므로 중간값인 `small_pq`의 가장 큰 값을 출력한다.

 

1. 우선순위 큐를 정의한다.
        1. `small_pq`: 가장 큰 값을 가져오는 우선순위 큐
        2. `big_pq`: 가장 작은 값을 가져오는 우선순위 큐
2. 제일 첫 입력을 `small_pq`에 넣고, 이를 출력한다.
3. `N-1`만큼 반복하며 입력을 받는다.
        1. 입력을 받아 `target`에 저장한다.
        2. `small_pq`의 제일 큰 값보다 `target`이 크다면, `big_pq`에 `target`을 넣는다.
                1. `target`을 넣은 후 `big_pq`의 사이즈가 `small_pq`사이즈 보다 크다면, `big_pq`의 제일 작은 원소를 빼서 `small_pq`에 넣는다.
        3. `small_pq`의 제일 큰 값보다 `target`이 작거나 같다면, `small_pq`에 `target`을 넣는다.
                1. `target`을 넣은 후 `small_pq`의 사이즈가 `big_pq`사이즈+1한 값보다 크다면, `small_pq`의 제일 큰 원소를 빼서 `big_pq`에 넣는다.
        4. `target`을 우선순위 큐에 넣었다면, `small_pq`의 제일 큰 원소를 출력한다.

---

💻 전체 코드

 

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine()) - 1;

        PriorityQueue<Integer> small_pq = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> big_pq = new PriorityQueue<>();

        small_pq.offer(Integer.parseInt(br.readLine()));
        sb.append(small_pq.peek()).append("\n");

        while (0 < N--) {
            int target = Integer.parseInt(br.readLine());
            if (small_pq.peek() < target) {
                big_pq.offer(target);
                if (small_pq.size() < big_pq.size()) {
                    small_pq.offer(big_pq.poll());
                }
            } else {
                small_pq.offer(target);
                if (big_pq.size() + 1 < small_pq.size()) {
                    big_pq.offer(small_pq.poll());
                }
            }
            sb.append(small_pq.peek()).append("\n");
        }
        System.out.print(sb);
    }
}

---

💫 리뷰

우선순위 큐를 잘 활용하면 됐던 문제! 옛날에 이런 비슷한 문제를 풀었던 것 같아서 풀이법이 바로 생각났다.

이래서 꾸준히 여러 문제를 풀어봐야한다..!!! 📚🤓