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

1. 문제

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

1655번: 가운데를 말해요

2. 접근방법

불러준 숫자의 가운데 숫자를 찾아야 한다.

 

우선순위큐 2개를 이용해서 가운데 숫자보다 작은 숫자들과 큰 숫자들을 각각 관리해주면 된다.

살짝 웹페이지 뒤로가기 기능과 비슷한 느낌

 

1234 5 6789

작은 수들에서는 max heap

큰 수들에서는 min heap으로 관리하여

min heap 과 max heap의 크기를 조건에 맞게 유지하면서 가운데 값을 구하면 된다.

 

tip) 출력이 10만건 일어나기 때문에 StringBuilder에 담아서 한번에 출력하자

3. 자바 코드

package backjoon;

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

public class P1655가운데를말해요 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
        PriorityQueue<Integer> right = new PriorityQueue<>();
        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            int mid = left.peek() == null ? 0 : left.peek();

            if(num < mid) left.add(num);
            else right.add(num);

            if (left.size() > right.size() + 1) right.add(left.poll());
            else if(left.size() < right.size()) left.add(right.poll());
            answer.append(left.peek()).append("\n");
        }
        System.out.println(answer);
    }
}

4. 마치며

아이디어가 재밌는 문제