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

문제

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

1655번: 가운데를 말해요

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

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

 

풀이

최소힙, 최대힙을 2개 만들어서 풀었다. 

항상 maxHeap의 사이즈를 minHeap의 사이즈와 같거나 +1 크게 유지하는 것을 염두하면서, 들어오는 값을 처리하면 답을 구할 수 있다.  maxHeap의 사이즈를 위와 같이 유지하면 중간 값은 항상 maxHeap의 첫 번째 값을 리턴해주면 된다.

 

1. maxHeap에 첫번째 값을 넣는다. 

2. maxHeap과 minHeap의 사이즈가 같은 경우 

현재 숫자와 중간값을 비교한다.

• 만약 현재 수가 maxHeap과 minHeap 의 첫 번째 값 사이에 있거나 maxHeap의 중간 값과 같거나 작을 경우, maxHeap에 넣어준다. 
• 그렇지 않은 경우 minHeap의 첫 번째 값을 maxHeap에 옮겨 넣은 후, 현재 수를 minHeap에 넣는다. 

2. maxHeap과 minHeap의 사이즈가 같지 않은 경우 (maxHeap의 사이즈가 큰 경우)

현재 숫자와 중간값을 비교한다.

• 만약 현재 숫자가 중간 값보다 같거나 클 경우,  minHeap에 넣는다.
• 만약 현재 숫자가 중간 값보다 작을 경우, maxHeap의 첫 번째 값을 minHeap으로 옮겨 넣은 후, 현재 수를 maxHeap에 넣는다.

 

 

1, 5, 2, 10, -99, 7, 5 를 예를 들어보자 

 

1) 입력: 1

maxHeap	minHeap
1

중간값: 1

 

2) 입력: 5

maxHeap	minHeap
1	5

중간값: 1

 

2) 입력: 2

maxHeap	minHeap
2
1	5

중간값: 2

 

2) 입력: 10

maxHeap	minHeap
2	5
1	10

중간값: 2

 

2) 입력: -99

maxHeap	minHeap
2
1	5
-99	10

중간값: 2

 

2) 입력: 7

maxHeap	minHeap
2	5
1	7
-99	10

중간값: 2

 

2) 입력: 5

maxHeap	minHeap
5
2	5
1	7
-99	10

중간값: 5

 

소스코드

package heap;

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

public class BOJ1655 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>((o1, o2) -> o1-o2);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((o1, o2) -> o2-o1);

        int N = Integer.parseInt(br.readLine());
        for(int i = 0; i < N; i++){
            int x = Integer.parseInt(br.readLine());
            if(maxHeap.isEmpty()){
                maxHeap.offer(x);
                bw.write(maxHeap.peek() + "\n");
                continue;
            }
            if(maxHeap.size() == minHeap.size()){
                if(x <= maxHeap.peek() || (maxHeap.peek() <= x && x <= minHeap.peek())){
                    maxHeap.offer(x);
                } else {
                    maxHeap.offer(minHeap.poll());
                    minHeap.offer(x);
                }
            } else {
                if(maxHeap.peek() <= x){
                    minHeap.offer(x);
                } else {
                    minHeap.offer(maxHeap.poll());
                    maxHeap.offer(x);
                }

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