[백준] 11286 절댓값 힙(실버1) - 힙(Heap), 우선순위 큐(PriorityQueue)

문제

• 입력 값이 0이 아니라면 배열에 삽입
• 입력 값이 0이라면 절댓값이 가장 작은 값 출력하고 제거
• 만약 절댓값이 0이 아닌 값이 여러 개라면 그중 가장 작은 값을 출력하고 제거

예제

코드

시도1 - O

• 절댓값을 저장할 최소 힙(우선순위 큐)를 선언한다.
• [절댓값, 최소힙] 형태의 해시맵을 선언한다.

1. N 크기만큼 순회하며 입력을 받는다.
2. 0이 아닌 값을 입력받으면
   • 힙에 입력 값이 존재하는지 확인
     • 존재한다면
       • 해시맵의 우선순위 큐 value에 입력 값 저장
     • 존재하지 않는다면
       • 힙에 절댓값 저장
       • 해시맵의 Key로 절댓값 / value로 입력 값 힙 저장
3. 0을 입력받으면
   • 절댓값 힙이 비어있는지 확인
     • 비어있지 않다면
       • 최소 절댓값 poll
       • key가 최소 절댓값인 해시맵의 value를 poll하여 반환
     • 비어있다면
       • 0 반환

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

public class _11286{ // Main으로 바꿔서 제출해야 함
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> absolute_pq = new PriorityQueue<>();
        HashMap<Integer, PriorityQueue<Integer>> hm = new HashMap<>();
        int N = Integer.parseInt(br.readLine());

		// 1. ----------------------------------------------------
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
	        // 2. ----------------------------------------------------
            if (num != 0) {
	            absolute_pq.add(Math.abs(num));
                if (!hm.containsKey(Math.abs(num))) {
                    PriorityQueue<Integer> pq = new PriorityQueue<>();
                    pq.offer(num);
                    hm.put(Math.abs(num), pq);
                    // hm.put(Math.abs(num), new PriorityQueue(num));
                }
                else
                    hm.get(Math.abs(num)).offer(num);
            }
            // 3. ----------------------------------------------------
            else { // 0
                if (!absolute_pq.isEmpty()) {
                    int min = absolute_pq.poll();
                    System.out.println(hm.get(min).poll());
                }
                else   
                    System.out.println(0);
                
            }
        }
    }
}

시도2 - O

우선순위 큐를 정의할 때 Comparator 인터페이스를 이용하여 우선순위를 설정할 수 있었다 .... ??

저번에 비슷한 문제가 있었던 것 같은데 기억 좀 하자 ^^

• 최소 힙을 선언한다.
  • 입력 값의 절댓값과 힙에 있는 요소들의 절댓값을 비교
    • 입력 값의 절댓값 > 힙에 있는 요소들의 절댓값 -> 힙에 있는 요소들의 절댓값이 우선
    • 입력 값의 절댓값 < 힙에 있는 요소들의 절댓값 -> 입력 값의 절댓값이 우선
    • 입력 값의 절댓값 == 힙에 있는 요소들의 절댓값 -> 원래 값이 작은 값이 우선
• 입력 값이 0이면
  • 0 반환
• 입력 값이 0이 아니면
  • 최소 힙에 입력 값 삽입

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

public class Backjoon11286 {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
            int abs1 = Math.abs(o1);
            int abs2 = Math.abs(o2);

            if(abs1 == abs2) return o1 > o2 ? 1 : -1;
            return abs1 - abs2;
        });
		// 1. ----------------------------------------------------
        for(int i = 0 ; i < n; i++){
            int val = Integer.parseInt(br.readLine());
            // 2. ----------------------------------------------------
            if(val == 0){
                if(queue.isEmpty()) System.out.println("0");
                else System.out.println(queue.poll());
			// 3. ----------------------------------------------------
            }else{
                queue.add(val);
            }
        }
    }
}

결론

우선순위 큐를 선언할 때 Comparator 인터페이스를 이용하여 우선순위를 설정할 수 있다.
return값에 따라 우선순위를 설정한다.

• return 값은 3가지로 나뉜다.
  • 음수: 첫 번째 요소가 두 번째 요소보다 우선순위가 높음
  • 0: 두 요소의 우선순위가 같음
  • 양수: 첫 번째 요소가 두 번째 요소보다 우선순위가 낮음

아래 예시를 보자

• 입력 값(o1)의 절댓값과 우선순위 큐의 요소들(o2)의 절댓값이 같을 때
  • 입력 값 > 요소 값: 양수(1) 반환 -> 입력 값의 우선순위가 요소 값의 우선순위보다 낮음
  • 입력 값 < 요소 값: 음수(-1) 반환 -> 입력 값의 우선순위가 요소 값의 우선순위보다 높음
• 입력 값(o1)의 절댓값과 우선순위 큐의 요소들(o2)의 절댓값이 다를 때
  • 입력 값의 절댓값 > 요소 값의 절댓값: 양수 반환 -> 입력 값의 우선순위가 요소 값의 우선순위보다 낮음
  • 입력 값의 절댓값 < 요소 값의 절댓값: 음수 반환 -> 입력 값의 우선순위가 요소 값의 우선순위보다 높음

PriorityQueue<Integer> queue = new PriorityQueue<>(**이부분**)

PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
            int abs1 = Math.abs(o1);
            int abs2 = Math.abs(o2);

            if(abs1 == abs2) return o1 > o2 ? 1 : -1;
            return abs1 - abs2;
        });

꼭 기억하자 !!!