우선순위 큐(11279, 1927, 11286, 1655)

[최대 힙 _ 11279]

 

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Problem_11279 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        for(int i=0; i<N; ++i){
            int num = scanner.nextInt();
            if(num > 0){
                priorityQueue.offer(num);
            }
            else if(num == 0){
                System.out.println(priorityQueue.size() == 0 ? 0 : priorityQueue.poll());
            }
        }
    }
}

 

 

[최소 힙 _ 1927]

 

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Problem_1927 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        for(int i=0; i<N; ++i){
            int num = scanner.nextInt();
            if(num > 0){
                priorityQueue.offer(num);
            }
            else if(num == 0){
                System.out.println(priorityQueue.size() == 0 ? 0 : priorityQueue.poll());
            }
        }
    }
}

 

 

[절댓값 힙 _ 11286]

 

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Problem_11286 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //절댓값 기준으로 오름차순 정렬
                if(Math.abs(o1) > Math.abs(o2)){
                    return 1;
                }
                else if(Math.abs(o1) == Math.abs(o2)) {
                    if(o1 > o2) return 1;
                    else if(o1 == o2) return 0;
                    else return -1;
                }
                else return -1;
            }
        });

        for(int i=0; i<N; ++i){
            int num = scanner.nextInt();
            if(num != 0){
                priorityQueue.offer(num);
            }
            else if(num == 0){
                System.out.println(priorityQueue.size() == 0 ? 0 : priorityQueue.poll());
            }
        }
    }
}

 

 

[가운데를 말해요 _ 1655]

 

 

* 조건

1. 숫자를 하나씩 외치게 되면 외쳐진 수들을 누적해간다
2. 누적된 때마다 오름차순 정렬된 상태에서 가운데 값 (중간값)을 출력한다

 

 

* 알고리즘

• Max 힙
• Min 힙

 

 

* 로직

• 중간 값을 기준으로 작은 수들을 관리하는 곳을 Max 힙으로 설정한다(내림차순, 루트는 최댓값)
• 중간 값을 기준으로 큰 수들을 관리하는 곳을 Min 힙으로 설정한다(오름차순, 루트는 최솟값)
• 숫자가 주어지면 우선적으로 Min 힙에 넣는다
• 만약 Max힙과 Min힙의 사이즈 합이 홀수라면 
  • Min 힙에 있는 루트를 Max 힙에 넣는다
• 만약 사이즈 합이 짝수이고
  • Max 힙에 있는 루트 값 > 외쳐진 숫자 => 서로 바꿔준다
  • 그렇지 않다면 그대로 상태를 유지한다
• Max 힙에 있는 루트 값을 출력한다

 

import java.io.*;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Problem_1655 {

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

        int N = Integer.parseInt(br.readLine());

        //중간값이 루트(중간값보다 작은 값들을 관리)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        //중간값보다 크거나 같은 값이 루트(중간값보다 큰 값들을 관리)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

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

            //만약 사이즈의 합이 짝수이고
            if((maxHeap.size() + minHeap.size()) % 2 == 0){
                //새로 입력된 num이 max의 top 값보다 작다면 -> 위치를 서로 바꾼다
                if(num < maxHeap.peek()){
                    minHeap.offer(maxHeap.poll());
                    maxHeap.offer(minHeap.poll());
                }
            }

            //사이즈 합이 홀수라면 -> min의 top 값을 max로 넣는다
           else{
                maxHeap.offer(minHeap.poll());
            }

           System.out.println(maxHeap.peek());
        }
    }
}