[알고리즘] 백준 1665 가운데를 말해요 -우선순위큐(heap)- 자바

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

 

백준 우선순위큐 단계별 풀기의 마지막 단계의 문제를 풀었습니다.

풀다가 도저히 안풀려서 가장 깔끔하게 푸신 분의 코드를 보고 이해했습니다.

 

설명도 잘해놓으셨습니다.

dragon-h.tistory.com/6

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

 

풀이를 정리하자면 두 개의 최소힙, 최대힙을 사용하여 가운데를 찾아야하니 개수를 균형맞게 번갈아 숫자를 추가해줍니다.

숫자가 최소힙 ~ 최대힙 으로 나열시킨다고 상상하면 쉽습니다. 여기서 최대힙의 가장 최댓값을 뽑는다면 그게 최댓값이 됩니다.

예를들어 최소힙에는  순서대로 9, 10   최대힙은 3, 2, 1 이라면 가운데 숫자는 3이 됩니다.   

이렇게 최소힙 ~ 최대힙의 순열을 유지하기 위해 최소힙의 최솟값이 최대힙의 최댓값보다  항상 크게 유지시켜줘야 합니다.

그래서 안그런경우 최소힙의 최솟값과 최대힙의 최댓값을 SWAP 해주어 순열을 유지할 수 있도록 해주는겁니다.

 

풀이는 다음과 같습니다.

[Java]

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

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> minHeap = new PriorityQueue<>(); //최소힙
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); //최대힙
        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(br.readLine());
            if (minHeap.size() == maxHeap.size()) { //두 힙에 번갈아 넣어줌
                maxHeap.offer(n);
            } else {
                minHeap.offer(n);
            }
            if (!minHeap.isEmpty() && !maxHeap.isEmpty()) {
                if (minHeap.peek() < maxHeap.peek()) {
                    //maxHeap의 최댓값이 minHeap의 최솟값 보다 큰 경우 균형을 맞추기 위해 swap
                    int tmp = minHeap.poll();
                    minHeap.offer(maxHeap.poll());
                    maxHeap.offer(tmp);
                }
            }
            System.out.println(maxHeap.peek());
        }
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!