백준_1655_가운데를말해요

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

https://gh402.tistory.com/32

입력한 값의 작은 값을 담는 공간하나 큰 값을 담는 공간하나
데이터 수를 일정하게 유지시키며 작은 값을 추출!

-> 왜 더 작은 값 추출?
짝수개이면 가운데 둘중에 작은 수를 추출하기 때문

풀이 1

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

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

        for(int i = 0 ; i < N; i++){
            int num = Integer.parseInt(br.readLine());

            if(minHeap.size() == maxHeap.size()) {
                maxHeap.offer(num); // 사이즈가 같으면 max에 넣음 => 무조건 max의 peek를 꺼내서 출력하기 위함
            } else{
                minHeap.offer(num); // 사이즈가 다르면 min에 넣음 => max와 min의 크기를 맞추기 위해 , 항상 max가 크거나 같음
            }

            if(!minHeap.isEmpty() && !maxHeap.isEmpty())
                if(minHeap.peek() < maxHeap.peek()){ // max의 peek가 더 작아야 max에서만 조건에 맞는 값 추출가능
                    int tmp = minHeap.poll();
                    minHeap.offer(maxHeap.poll());
                    maxHeap.offer(tmp);
                }

            sb.append(maxHeap.peek() + "\n"); // 처리 이후 출력에 담음
        }
        System.out.println(sb);
    }
}

우선 순위 큐를 활용한 문제

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 큰 수 우선순위 큐

• PriorityQueue는 기본적으로 최소 힙(Min-Heap)으로 작동하지만, Collections.reverseOrder()를 사용하면 최대 힙(Max-Heap)으로 동작하게 된다! 이 경우, peek() 메소드는 힙에서 가장 큰 값을 반환!
• MaxHeap : 👉 1 2 3 4 5 👉
• MinHeap : 👉 5 4 3 2 1 👉

📌 수의 크기? 보다는 두 힙의 갯수를 맞추는게 중요한 문제!

• 처음에는 minHeap의 peek()와 비교해가며 수를 넣어야된다고 생각했는데 가운데 수 를 구하는 문제이므로 두 힙의 갯수를 신경써야했음!

🤔 큐를 채우는 방식의 차이로 인한 2가지 풀이!

		for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            if (maxHeap.size() == minHeap.size()) {
                maxHeap.offer(num);
            } else {
                minHeap.offer(num);
            }

            // maxHeap의 루트가 minHeap의 루트보다 크다면 두 루트를 교환
            if (!maxHeap.isEmpty() && !minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
                int maxRoot = maxHeap.poll();
                int minRoot = minHeap.poll();
                maxHeap.offer(minRoot);
                minHeap.offer(maxRoot);
            }

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

• 숫자를 maxHeap과 minHeap에 번갈아가며 추가하는 것! 추가 후 maxHeap의 루트가 minHeap의 루트보다 클 경우, 두 peek를 교환하여 힙의 균형을 맞추는 방식

		for(int i = 0; i < N; i++){
            int num = Integer.parseInt(br.readLine());

            maxHeap.offer(num);

            // maxHeap의 최대값을 minHeap으로 이동
            if (!maxHeap.isEmpty()) {
                minHeap.offer(maxHeap.poll());
            }

            // maxHeap의 크기와 minHeap의 크기를 맞추기
            if (maxHeap.size() < minHeap.size()) {
                maxHeap.offer(minHeap.poll());
            }

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

• 숫자를 maxHeap에 추가한 후, maxHeap의 peek를 minHeap으로 이동시킴. 이후, minHeap의 크기가 maxHeap보다 크다면 minHeap의 루트를 다시 maxHeap으로 이동하여 힙의 균형을 맞추는 방식

👉 2번째 방식이 더욱 간결하고 peek를 교환하는 오버헤드가 없을 것 같다!

최종풀이

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 큰 수 우선순위 큐
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 작은 수 우선순위 큐

        for(int i = 0; i < N; i++){
            int num = Integer.parseInt(br.readLine());

            maxHeap.offer(num);

            // maxHeap의 최대값을 minHeap으로 이동
            if (!maxHeap.isEmpty()) {
                minHeap.offer(maxHeap.poll());
            }

            // maxHeap의 크기와 minHeap의 크기를 맞추기
            if (maxHeap.size() < minHeap.size()) {
                maxHeap.offer(minHeap.poll());
            }
            
            sb.append(maxHeap.peek()).append("\n");
        }
        System.out.print(sb);
    }
}

1. maxHeap에 일단 넣기
2. maxHeap의 최대값을 minHeap으로 이동
3. maxHeap의 크기와 minHeap의 크기를 맞추기

-> minHeap은 maxHeap의 최댓값으로 채워지게 됨