백준/11286 절댓값 힙 / 우선순위큐, Comparator

절댓값 힙 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음) (하단 참고)

256 MB

31694

17683

14442

56.658%

문제

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

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

---

풀이

/*
절댓값 순서대로 정렬을 하고,
절대값이 가장 작은게 여러개일 경우 가장 작은값을 삭제해라 -> ex ( 절댓값 8이 가장 작은 절댓값일때 8과 -8이 있다면 -8을 삭제해라)

음수를 저장하는 최대힙 우선순위큐를 만들어서 큰값이 우선순위가 높게끔 하고
양수일때는 최소힙 우선순위큐를 만든다.

0이나오면 양쪽에서 값을 하나씩 뽑아서 절대값으로 바꾼후 값을 비교한다.
절대값이 더 작은쪽이 있다면 해당 우선순위큐에서 값을 제거하면서 출력한다.
절대값이 같다면 음수쪽 우선순위큐에서 값을 제거하고 출력한다.
 */

우선순위큐를 2개 만듦

음수저장하는큐 ( 최대힙)

양수저장하는큐  (최소힙)

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


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
    절댓값 순서대로 정렬을 하고,
    절대값이 가장 작은게 여러개일 경우 가장 작은값을 삭제해라 -> ex ( 절댓값 8이 가장 작은 절댓값일때 8과 -8이 있다면 -8을 삭제해라)

    음수를 저장하는 최대힙 우선순위큐를 만들어서 큰값이 우선순위가 높게끔 하고
    양수일때는 최소힙 우선순위큐를 만든다.

    0이나오면 양쪽에서 값을 하나씩 뽑아서 절대값으로 바꾼후 값을 비교한다.
    절대값이 더 작은쪽이 있다면 해당 우선순위큐에서 값을 제거하면서 출력한다.
    절대값이 같다면 음수쪽 우선순위큐에서 값을 제거하고 출력한다.
     */
    static PriorityQueue<Integer> negativeQueue = new PriorityQueue<>(Collections.reverseOrder()); // 음수 우선순위큐
    static PriorityQueue<Integer> positiveQueue = new PriorityQueue<>(); // 양수 우선순위큐
    static int n;

    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());
    }

    static void solve() throws IOException {

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

            if (input > 0) { //양수인경우
                positiveQueue.add(input);
            } else if (input < 0) { // 음수인경우
                negativeQueue.add(input);
            } else { //0인경우
                //둘다 비었을때는 0 출력
                //아니라면 한쪽만 비어있는 경우를 조심하며 비교한다.

                long negativeAbs = Integer.MIN_VALUE; // 값의 범위는 절대값으로 봄녀 음수가 양수보다 1더 크다는것을 잊으면 안된다. 
                long positiveAbs= Integer.MAX_VALUE;

                if (negativeQueue.isEmpty() && positiveQueue.isEmpty()) {
                    bw.write("0\n"); //0을 출력하고 반복문 다음으로 넘어가야한다.
                    continue;
                }
                if (!negativeQueue.isEmpty()) {
                    negativeAbs = negativeQueue.peek();
                }
                if (!positiveQueue.isEmpty()) {
                    positiveAbs = positiveQueue.peek();
                }
                negativeAbs = Math.abs(negativeAbs);
                positiveAbs = Math.abs(positiveAbs);

                if (negativeAbs > positiveAbs) { // 양수쪽이 절대값이 더 작다면 양수쪽 제거하고 출력
                    bw.write(positiveQueue.poll() + "\n");
                } else { //음수쪽이 절대값이 작거나, 절대값이 같은경우 음수쪽 제거하고 출력
                    bw.write(negativeQueue.poll() + "\n");
                }
            }

        }


    }

}

주의할점

https://keeeeeepgoing.tistory.com/126

Integer.Min_Value 를 Math.abs 했을때

다른 풀이 + 비교 기준 직접 설정

우선순위큐의 정렬 기준을 직접만들어서 풀이

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


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*

     */
    static PriorityQueue<Integer> absPriorityQueue; //절대값 우선순위큐
    static int n;

    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());
        absPriorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (Math.abs(o1) == Math.abs(o2)) { //절대값이 같다면
                    return o1 - o2; // 값 자체로 비교해서 오름차순
                } else {
                    return Math.abs(o1) - Math.abs(o2); // 아니면 절대값으로 비교해서 오름차순
                }
            }
        });
    }

    static void solve() throws IOException {

        for (int i = 0; i < n; i++) {
            int input = Integer.parseInt(br.readLine());
            if (input == 0) {
                if (absPriorityQueue.isEmpty()) {
                    bw.write("0\n");
                } else {
                    bw.write(absPriorityQueue.poll() + "\n");
                }
            } else {
                absPriorityQueue.add(input);
            }

        }


    }

}