[JAVA] BOJ 백준 1655번 - 가운데를 말해요

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1655번: 가운데를 말해요

---

2. 내가 푼 방법

가운데 값을 찾기 위해 두 개의 우선순위 큐를 이용했다. 먼저 bigger는 max 값이 가장 먼저 나와야 하므로 내림차순으로 된 우선순위 큐이고, smaller는 min 값이 가장 먼저 나와야하므로 오름차순으로 된 우선순위 큐이다.

 

전체적인 그림은 bigger와 smaller를 이었을 때 가운데로 값이 빠져나와서 확인할 수 있어야 하고, 중간 값을 찾기 위해서는 두 개의 큐 사이즈가 항상 같아야한다. 

 

---

3. 자바 풀이

import java.util.*;
import java.io.*;

class Main {
    static PriorityQueue<Integer> bigger;
    static PriorityQueue<Integer> smaller;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        bigger = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순, 최대 값을 가지고 있음
        smaller = new PriorityQueue<>(); // 오름차순, 최소 값을 가지고 있음

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

            if (bigger.size() == smaller.size()) bigger.add(num);
            else smaller.add(num);

            if (!bigger.isEmpty() && !smaller.isEmpty()) {
                if (bigger.peek() > smaller.peek()) {
                    smaller.add(bigger.poll());
                    bigger.add(smaller.poll());
                }
            }

            bw.write(bigger.peek()+"\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

 

---

4. 결과 및 회고

처음에는 두 개의 스택으로 풀었는데 이 문제는 정렬이 반드시 필요했기에 우선순위 큐가 필요했던 문제라고 생각한다. 

문제를 풀 때 내 풀이가 정답이 아닐 수도 있다는 의심과,, 조금 더 자신 있게 풀이를 하기 위해 많이 풀어야 할 것 같당.