코딩테스트/백준

[백준 - 11286] 절댓값 힙 구현하기 .java

머밍 2024. 7. 13. 17:06

 

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

 

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

  1. 배열에 정수 x (x ≠ 0)를 넣는다.
  2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1 

18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0

예제 출력 1 

-1
1
0
-1
-1
1
1
-2
2
0

 

Solution

<문제 분석>

N의 범위가 100,000이므로 O(nlogn) 시간 복잡도 알고리즘으로 풀 수 있다. 

다만, 데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요 -> 우선순위 큐

이 문제에선 절댓값이 같은 경우 음수를 우선해야 한다.

 

  1. 정수 = 0 : 비어있는 큐면 0을 출력, 그렇지 않으면 절댓값이 최소인 값을 출력(절댓값이 같을 경우 음수 우선)
  2. 정수 != 0: add 로 새로운 값 추가 -

어려운 점은 우선순위 큐에서 어떻게 정렬 기준을 새워야하는지였다.

// 우선순위 큐를 선언. 
        // 숫자들의 절대값을 기준으로 정렬
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> {
            int first_abs = Math.abs(a);
            int second_abs = Math.abs(b);

            // 두 숫자의 절대값이 같은 경우, 실제 값을 비교하여 정렬
            if (first_abs == second_abs) {
                return a > b ? 1 : -1; // a가 b보다 크면 1, 아니면 -1 반환
            } else {
                return first_abs - second_abs; // 절대값이 작은 것이 우선
            }
        });

 

 

  • 절대값이 같은 경우:
    • if (first_abs == second_abs) {
      • 절대값이 같은 경우, 실제 값으로 비교
    • return a > b ? 1 : -1;
      • a가 b보다 크면 1을 반환하여 b가 a보다 우선. 그렇지 않으면 -1을 반환하여 a가 b보다 우선. 즉, 음수가 양수보다 우선.
  • 절대값이 다른 경우:
    • else {
      • 절대값이 다른 경우, 절대값을 기준으로 비교합니다.
    • return first_abs - second_abs;
      • first_abs가 second_abs보다 작으면 음수를 반환하여 a가 b보다 우선. first_abs가 second_abs보다 크면 양수를 반환하여 b가 a보다 우선

 

이 부분에서 먼저 두 수를 절댓값으로 비교하고 만약 절댓값이 같을때 숫자 1과 -1이 비교 결과에 따라 정렬 순서를 결정하는 데 사용.

이 구문은 정렬 함수에서 두 값 a와 b를 비교한 결과에 따라 반환 값을 다르게 설정.
정렬 함수에서 이와 같은 반환 값은 정렬 알고리즘이 요소들을 비교하고 순서를 결정할 때 사용됨.

 

 

우선한다는 것은 정렬이나 큐에서 앞에 나온다는 것을 의미.
Comparator에서 반환값이 양수이면 두 번째 인수가 첫 번째 인수보다 우선.
Comparator에서 반환값이 음수이면 첫 번째 인수가 두 번째 인수보다 우선.

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 효율적 입력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 번째 줄에서 숫자의 개수 n을 입력
        int n = Integer.parseInt(br.readLine());

        // 우선순위 큐를 선언. 
        // 숫자들의 절대값을 기준으로 정렬
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> {
            int first_abs = Math.abs(a);
            int second_abs = Math.abs(b);

            // 두 숫자의 절대값이 같은 경우, 실제 값을 비교하여 정렬
            if (first_abs == second_abs) {
                return a > b ? 1 : -1; // a가 b보다 크면 1, 아니면 -1 반환
            } else {
                return first_abs - second_abs; // 절대값이 작은 것이 우선
            }
        });

        // n개의 숫자를 처리하기 위한 반복문
        for (int i = 0; i < n; i++) {
           
            int num = Integer.parseInt(br.readLine());
            
            // 입력된 숫자가 0인 경우
            if (num == 0) {
                // 큐가 비어 있으면 0을 출력
                if (q.isEmpty()) {
                    System.out.println("0");
                } else {
                    // 큐가 비어 있지 않으면, 큐에서 최우선 요소를 꺼내서 출력
                    System.out.println(q.poll());
                }
            } else {
                // 입력된 숫자가 0이 아닌 경우, 큐에 숫자를 추가
                q.add(num);
            }
        }
    }
}