[백준 / Java] 11286번: 절댓값 힙 (실버1)

문제 풀이 날짜: 2023.08.09
포스트 작성일: 2023.08.09

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 11286번: 절댓값 힙 (실버1)

 

키워드

우선순위 큐, Comparator

 

풀이 접근법

• 원본 값(value)과 절댓값(abs)을 동시에 손쉽게 참조할 수 있도록 Node 클래스를 정의하였다.
• 2가지 정렬 기준을 가지고 Comparator를 구현하는 것이 중요한 문제이다. 첫 번째 정렬 기준이 동일하다면 0을 반환하지 않고, 그 다음으로 매길 정렬 기준을 구현해준다.
• 람다식으로 구현할 경우, 두 번째 정렬 조건(if문)에 걸리면 먼저 return해주고 조건에 걸리지 않으면 첫 번째 정렬 기준을 따르도록 작성하면 compare 메소드를 간단하고 빠르게 구현할 수 있다.
• 아래의 람다식을 compare 메소드로 풀어서 써보면 다음과 같다.

PriorityQueue<Node> pq = new PriorityQueue<>( new Comparator<Node>() {
			@Override
			public int compare(Node o1, Node o2) {
				if(o1.abs > o2.abs) {
					return 1;
				}
				else if (o1.abs < o2.abs) {
					return -1;
				}
				else { //절댓값이 같다면
					if(o1.value > o2.value) {
						return 1; //원본값이 작은 것을 반환한다
					}
					else {
						return -1;
					}
				}
			}
		});

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		int curr;
		PriorityQueue<Node> pq = new PriorityQueue<>(
				(o1, o2) -> {
					if(o1.abs == o2.abs) return o1.value - o2.value;
					return o1.abs - o2.abs;
				});
		
		for(int i = 0; i < N; i++) {
			curr = Integer.parseInt(br.readLine());
			
			if(curr == 0) {
				if(!pq.isEmpty())
					sb.append(pq.poll().value).append("\n");
				else
					sb.append(0).append("\n");
				continue;
			}
			
			Node n = new Node(curr, Math.abs(curr));
			pq.add(n);
		}
		
		System.out.println(sb);
	}

}

class Node {
	public int value;
	public int abs;
	
	public Node(int value, int abs) {
		this.value = value;
		this.abs = abs;
	}
}

 

---

 

 

git 링크

(git 링크 첨부)