[자료구조2] 백준 11286 절댓값 힙

11286번: 절댓값 힙

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

 

# 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입출력을 위한 BufferedReader 와 StringBuilder
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 연산의 개수 N
        long n = Long.parseLong(br.readLine());

        // 절댓값이 작은 수부터 꺼낼 양수용/음수용 우선순위 큐
        // 음수 큐에서는 큰 숫자일수록 절댓값이 작으므로 reverseOrder() 옵션 적용
        PriorityQueue<Long> q_plus = new PriorityQueue<>();
        PriorityQueue<Long> q_minus = new PriorityQueue<>(Collections.reverseOrder());

        for (long i = 0; i < n; i++) {
            long num = Long.parseLong(br.readLine());

            // 입력이 양수이면 양수 큐, 음수이면 음수 큐에 추가
            if (num > 0) {
                q_plus.offer(num);
            } else if (num < 0) {
                q_minus.offer(num);
            } else {
                // 입력이 0일 때
                // 두 큐가 모두 빈 경우 0 출력
                if (q_plus.isEmpty() && q_minus.isEmpty()) {
                    sb.append("0").append("\n");
                } else if (q_plus.isEmpty()) {
                    sb.append(q_minus.poll()).append("\n");
                } else if (q_minus.isEmpty()) {
                    sb.append(q_plus.poll()).append("\n");
                } else {
                    // 두 큐 모두 원소를 가지고 있는 경우
                    // 각 큐에서 peek하여 절댓값을 비교한 후 가장 작은 수 출력
                    if (q_plus.peek() < -q_minus.peek()) {
                        sb.append(q_plus.poll()).append("\n");
                    } else if (q_plus.peek() > -q_minus.peek()) {
                        sb.append(q_minus.poll()).append("\n");
                    } else {
                        // 절댓값이 동일할 경우 q_minus 의 원소 출력
                        sb.append(q_minus.poll()).append("\n");
                    }
                }
            }
        }

        System.out.println(sb);

        // Reader 버퍼 닫기
        br.close();
    }
}

• 절댓값을 비교하기 위해 우선순위 큐를 2개 운영했다.
• 정답 판정은 받았지만 상당히 찜찜하고 비효율적으로 코드를 짠 느낌이 들어 찾아보니 Comparator 라는 api를 이용하는 방법이 있다고 한다.

 

아래는 조금 더 효율적으로 문제를 해결하는 코드이다.

정렬 기준을 정하는 Comparator 를 이용하기 위해서 이 인터페이스 안에 있는 compare 라는 추상메소드를 구현해주어야 한다고 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
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> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				//절대값 기준으로 앞 값이 더 크다면 자리를 바꿔준다.
				if(Math.abs(o1) > Math.abs(o2)) {
					return Math.abs(o1) - Math.abs(o2);
				//절대값 기준으로 두 값이 같다면 음수를 앞으로 보내준다.
				}else if(Math.abs(o1) == Math.abs(o2)) {
					return o1 - o2;
				}else {
					return -1;
				}
			}
		});
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			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.offer(x);
			}
		}
		System.out.println(sb);
	}

}

 

또는 다음과 같이 간단하게 작성할 수도 있다.

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> pq = new PriorityQueue<>((o1, o2) ->
                Math.abs(o1) == Math.abs(o2) ? Integer.compare(o1, o2) : Integer.compare(Math.abs(o1), Math.abs(o2))
        );

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

            if (x == 0) {
                if (!pq.isEmpty()) {
                    System.out.println(pq.poll());
                } else {
                    System.out.println(0);
                }
            } else {
                pq.add(x);
            }
        }

    }

}

 

두 코드는 각각 아래 블로그를 참고하였다 :D

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

 

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