절댓값 힙 구현하기(백준 11286)

문제 분석하기

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

▪ O(nlogn) → 100,000 × log₂100,000
- log₂100,000 ≈ 17
- 즉 100,000 × 17 = 1,700,000번 연산
👉 170만 번이면 컴퓨터는 0.01초도 안 걸림. 매우 빠름.
데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요하므로 우선순위 큐를 활용
단, 이 문제는 절댓값 정렬이 필요하므로 우선순위 큐의 정렬 기준을 직접 정의해야함

손으로 풀어 보기

✏️문제 푸는 순서

1️⃣ x = 0 일 때,

큐가 비어 있을 때는 0 출력, 비어있지 않을 때는 절댓값이 최소인 값을 출력(단, 절댓값이 같으면 음수를 우선 출력)

2️⃣ x=0 아니면,

add로 큐에 새로운 값을 추가하고 우선순위 큐 정렬 기준으로 자동 정렬

슈도코드 작성

우선순위 큐 선언
- 절댓값 기준으로 정렬되도록 설정
- 단, 절댓값 같으면 음수 우선 정렬

for(N번) {
	0: 큐 비어있으면 0, 아니면 큐의 front poll()
	0 아니면: 새로운 데이터 큐에 add()
}

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStremReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		// 커스텀 Queue
		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; // 1: o1을 뒤로(오름차순), -1: o1을 앞으로(내림차순)
			} // 절댓값 같은 경우 음수 우선 정렬
			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);
			}
		}	
	}
}

📌 사용된 메서드

Math.abs(Int num): num 을 절댓값으로 반환
compare 함수

▪ O(nlogn) → 100,000 × log₂100,000