[백준 실버 1] 11286번: 절댓값 힙

문제

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

11286번: 절댓값 힙

 

풀이

• 0이 아닌 정수 x를 배열에 넣는다.
• 배열에서 절댓값이 가장 작은 값을 출력하고 제거한다.
• 절댓값이 가장 작은 값이 여러 개라면, 그중에 가장 작은 수를 출력하고 제거한다.
• 0이 아닌 수가 주어지면 배열에 입력하고, 0이 주어진다면 위 규칙에 맞게 수를 출력하면 된다.
• 연산의 개수는 1보다 크고 100,000보다 작다.
• 입력되는 정수 x는 -2^31보다 크고 2^31보다 작다.

출력할 때마다 배열에서 가장 작은 수를 찾는다면 무조건 시간 초과가 일어난다. 그렇기 때문에 Priority Queue(우선순위 큐)를 사용해 우선순위가 높은 데이터가 먼저 출력되도록 해야 한다. 여기서 우선순위는 절댓값이 작고, 크기가 작은 수 순으로 높다.

 

Priority Queue는 기본적으로 오름차순 정렬로 우선순위가 정해져 있다. 그렇기 때문에 문제의 조건을 만족하는 우선순위를 정의해야 한다. 이때 Comparable과 Comparator 인터페이스를 사용해 객체를 비교할 수 있도록 해야 한다. Comparable은 compareTo(T o) 메서드를 사용하고 Comparator는 compare(T o1, T o2) 메서드를 사용한다. compareTo는 자신과 매개변수 T o를 비교하는 것이고, Comparator는 주어진 두 객체를 비교하는 것이다.

 

여기선 Comparator를 사용해서 문제를 풀어보도록 한다.

Comparator 인터페이스를 구현한 클래스는 반드시 compare(T o1, T o2) 메서드를 재정의 해야 한다. 이때 출력값은 o1이 크다면 양수, o2가 크다면 음수, 그리고 같다면 0이 출력된다.

Comparator<Integer> comparator = new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        ...
    }
};

 

여기서 들었던 의문은 객체를 비교하는 것이 정렬과 어떤 관련이 있냐는 것이었다.

자세한 내용은 아래 링크의 블로그를 참고하였다. 공부할 때 정말 큰 도움이 되는 블로그다.

https://st-lab.tistory.com/243

자바 [JAVA] - Comparable 과 Comparator의 이해

 

문제의 조건은 절댓값이 작고, 만약 절댓값이 같다면 더 작은 수를 출력한다고 되어 있다.절댓값이 작은 경우는 o1이 o2보다 작은 경우가 된다. 그러므로 o1과 o2의 위치를 바꿀 필요가 없기 때문에 음수를 출력한다. 절댓값이 같은 경우도 마찬가지로 o1과 o2를 비교하여 음수를 출력한다.

int abs1 = Math.abs(o1);
int abs2 = Math.abs(o2);

if (abs1 == abs2) {
    return o1 - o2;
}

return abs1 - abs2;

 

0이 아닌 정수가 입력되면 Priority Queue에 추가하고, 0이 입력되면 poll()을 사용해서 출력과 삭제를 동시에 해준다.

for (int i = 0; i < N; i++) {
    int input = Integer.parseInt(br.readLine());
    if (input == 0) {
        if (pq.isEmpty()) {
            sb.append(0).append("\n");
        } else {
            sb.append(pq.poll()).append("\n");
        }
        continue;
    }
    pq.add(input);
}

 

전체 코드 (Java)

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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;
			}

			return abs1 - abs2;
		});

		StringBuilder sb = new StringBuilder();

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

			if (input == 0) {
				if (pq.isEmpty()) {
					sb.append(0).append("\n");
				} else {
					sb.append(pq.poll()).append("\n");
				}
				
				continue;
			}
			
			pq.add(input);
		}
		
		System.out.println(sb);
	}
}

 

 

후기

힙과 우선순위 큐, Comparable과 Comparator까지 이 문제를 풀며 들었던 의문을 모두 정리하느라 오래 걸린 문제였다. 그래도 궁금한 부분을 모두 해소할 수 있어서 만족스러웠다.