[백준 1665] 가운데를 말해요 (Java)

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

1655번: 가운데를 말해요

 

풀이

배열이나 ArrayList를 이용하여 풀이를 시도하였더니 메모리초과, 시간초과 문제가 발생했다.

 

MaxHeap, MinHeap 개념을 이용하여 문제를 풀었다. (Heap은 PriorityQueue로 구현)

입력받는 숫자를 MaxHeap과 MinHeap에 번갈아 가면서 add를 하되,

MaxHeap의 첫번째 값과 MinHeap의 첫번째 값을 비교했을 때 (MaxHaep.peek() > MinHeap.peek())

Min쪽 값이 더 크다면 swap을 해준다.

이렇게 하게 되면 MaxHeap의 peek에 입력받은 값들의 중간 값이 들어오게 된다.

 

코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StringBuilder stringBuilder = new StringBuilder();

        int N = scanner.nextInt();

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.naturalOrder());

        for (int i = 0; i < N; i++) {
            int number = scanner.nextInt();

            if (i % 2 == 0) {
                maxHeap.add(number);
            } else {
                minHeap.add(number);
            }

            if (!maxHeap.isEmpty() && !minHeap.isEmpty()) {
                if (maxHeap.peek() > minHeap.peek()) {
                    int temp = maxHeap.poll();
                    maxHeap.add(minHeap.poll());
                    minHeap.add(temp);
                }
            }

            stringBuilder.append(maxHeap.peek())
                         .append("\n");
        }

        System.out.println(stringBuilder.toString());
    }
}

 

[참고]

https://devowen.com/246

백준 1655 / 최대힙(MaxHeap), 최소힙(MinHeap) / JAVA