관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/힙(우선순위큐)

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

막무가내막내 2020. 11. 9. 23:54
728x90

www.acmicpc.net/problem/1655

 

1655번: 가운데를 말해요

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1

www.acmicpc.net

 

 

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

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

 

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

dragon-h.tistory.com/6

 

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

개요 PriorityQueue를 이용하여 풀 수 있는 문제이다. 해당 자료구조에 대한 이해도가 없는 사람들은 기초 문제부터 풀고 오면 좋을 것이다. 문제를 읽어보면 오름차순 정렬을 했을 때 가운데 인덱

dragon-h.tistory.com

 

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

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

예를들어 최소힙에는  순서대로 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());
        }
    }
}

 

 

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

728x90
Comments