[큐] 절대값 힙

목차

1. 풀이

(1) 문제

백준 11286번, 절댓값 힙 : https://www.acmicpc.net/problem/11286

 

핵심키워드

1) 문제 내용

- 다음 연산을 지원하는 절댓값 힙 자료구조를 만들어라.

 -> 1. 배열에 정수 x (x ≠ 0) 를 넣는다.

 -> 2. 배열에 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절대값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

 

2) 입력

- 첫째 줄에 연산의 개수 N(1≤N≤100,000)이  주어진다.

- 둘째 줄에 배열에 들어갈 x가 주어진다.

 -> x가 0이 아니라면 배열에 x값을 추가

 -> x가 0이면 절대값이 가장 작은 값을 출력하고 배열에서 제거한다.

 -> 정수는 -231보다 크고, 231보다 작다

 

3) 출력

- 입력에서 0이 주어진 회수만큼 답을 출력한다.

- 만약 배열이 비어 있고 입력에 0이 주어지면 0을 출력한다.

 

(2) 풀이

- 제한시간이 1초이며, 연산의 개수 N(1≤N≤100,000)이므로 시간복잡도가 O(log n)인 알고리즘을 사용해야 한다.

- 우선순위 큐를 활용하여 접근하면 쉽게 풀 수 있다.

 

* 우선순위 큐 *

- 큐(Queue)는 선입선출(FIFO) 방식이지만, 우선순위 큐는 우선순위가 높은 데이터를 먼저 내보내는 방식이다.

- 데이터의 삽입 혹은 삭제 연산이 실행하기전에, 우선순위가 높은 데이터를 front로 보내는 연산이 이루어 진다. 그 과정에서 나머지 데이터들의 위치가 변경된다. 

 

출처 : https://www.programiz.com/dsa/priority-queue

 

2. 정답

1) 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));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> myQueue = new PriorityQueue<>((o1, o2) ->{
            int firstAbs = Math.abs(o1);
            int secondAbs = Math.abs(o2);
            if (firstAbs == secondAbs) { //절대값이 같은 경우 음수 우선
                return o1 > o2 ? 1 : -1;
            }
            return firstAbs - secondAbs; // 절대값이 작은 데이터 우선
        });

        for (int i = 0; i < N; i++) {
            int request = Integer.parseInt(br.readLine());
            if (request == 0) {
                if (myQueue.isEmpty()) {
                    System.out.println(0);
                } else {
                    System.out.println(myQueue.poll());
                }
            } else {
                myQueue.add(request);
            }
        }
    }
}

• 우선순위 큐 클래스는 Comparator를 커스텀할 수 있다. 

2) 내부 클래스에 Comparator를 상속받아 커스텀

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

public class Main {

    // 내부 클래스 AbsoluteValueComparator 정의
    static class AbsoluteValueComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer a, Integer b) {
            int absA = Math.abs(a);
            int absB = Math.abs(b);
            if (absA == absB) {
                return a - b; // 절댓값이 같으면 실제 값으로 비교
            }
            return absA - absB; // 절댓값 기준으로 비교
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // AbsoluteValueComparator를 사용하여 PriorityQueue를 생성
        PriorityQueue<Integer> pq = new PriorityQueue<>(new AbsoluteValueComparator());

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();

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

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

3. 참고

- Do it 알고리즘 코딩 테스트 자바 편(김종관)