[백준/JAVA] 11286번: 절댓값 힙

🔺 문제

11286번: 절댓값 힙

 

🔺 코드

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

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

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

        // 우선순위 큐 선언
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            int first_abs  = Math.abs(o1);
            int second_abs = Math.abs(o2);

            if(first_abs == second_abs)
                return o1 > o2 ? 1 : -1;    // 절댓값이 같다면 음수 우선출력
            else
                return first_abs - second_abs;  // 절댓값 기준 정렬
        });

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

            if(num == 0) {
                if(pq.isEmpty()) 
                    sb.append("0").append("\n");
                else
                    sb.append(pq.poll()).append("\n");
            }
            else {
                pq.add(num);
            }
        }

        System.out.println(sb.toString());
    }
}

✅ 해결 아이디어
- 우선순위 큐 → 정렬 기준 새로 적용

💥 유의사항

⇨ Compare 함수 구현 시, return 값으로 양수를 주면 순서를 바꾸겠다는 의미.

⇨ 절댓값이 같은 경우, 그 중 작은 값으로 오름차순 정렬 / 아닌 경우 절댓값이 작은 순서로 오름차순 정렬

---

🔺 다른 풀이들

- 풀이1) Compare 오버라이드

[백준/BOJ] 11286번 : 절댓값 힙 (JAVA / 자바)

메소드 사용자 정의하실 때 오버라이드를 사용하셨다.

 

 

- 풀이2) 우선순위 큐 정의할 때 삼항식 사용!

[백준 - Java] 11286번 : 절댓값 힙

 

 

+ 복습용

[백준 11286번] 절댓값 힙 (JAVA)

---

💬 느낀 점

사용자 정의 정렬 방법!을 잊지 말자.

 

 

(+ 6/13 2회독)

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());
        
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            int abs1 = Math.abs(o1);
            int abs2 = Math.abs(o2);
            
            if(abs1 == abs2) {      // 절댓값이 같으면 음수 우선 정렬
                return o1 - o2;
            } else {
                return abs1 - abs2; // 절댓값 기준 정렬
            }
        });
        
        while(N --> 0) {
            int x = Integer.parseInt(br.readLine());
            
            if(x == 0) {
                if(pq.isEmpty()) {
                    sb.append(0).append("\n");
                } else {
                    sb.append(pq.poll()).append("\n");
                }
            }
            else {
                pq.add(x);
            }
        }
        System.out.print(sb);
    }
}

 

 

 

---

(참고)

✔ 우선순위 큐 클래스 사용법

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리

---

 

+ 비슷한 문제

✔ 최소 힙

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

1927번: 최소 힙

✔ 최대 힙

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

11279번: 최대 힙