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

31 Jul 2023 in Algorithm on 자료 구조

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

풀이

숫자를 입력할 때마다 말했던 숫자들 중 중간값을 말해야한다.

PriorityQueue 2개를 사용해 left, right로 저장하고

left의 peek이 항상 중간값이 되도록 구현했다.

따라서, left는 내림차순으로 저장 및 출력했다.

left가 비어있거나 left의 peek보다 말한 숫자가 작으면 left에 넣었다. 그렇지 않은 경우는 right에 넣는다.

left 크기와 right 크기의 차이가 1보다 크면 left에서 빼서 right에 넣어주고,

right의 크기가 더 크면 right에서 빼서 left에 넣어주었다.

즉, left의 크기와 right의 크기의 차이가 0, 1이 되도록 유지했다.

그렇게해서 left의 peek값이 항상 중간값이 되도록 했다.

---

메모리: 33052KB

시간: 456ms

언어: Java 11

코드

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

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());
        PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));
        PriorityQueue<Integer> right = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            if (left.isEmpty() || left.peek() >= num) {
                left.add(num);
            } else {
                right.add(num);
            }

            int diff = left.size() - right.size();
            if (diff == 2) {
                right.add(left.poll());
            } else if (diff == -1) {
                left.add(right.poll());
            }

            sb.append(left.peek()).append("\n");
        }

        System.out.println(sb);
    }

}