백준 - 11286 ( 절대값 힙)

문제를 이해하는데 꽤나 오랜 시간이 걸렸는데 해결 방법은 엄청 쉬운 그런 문제였던 것이다. 

 

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

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());
		
        
        //우선순위 큐를 pq를 생성하고 
		PriorityQueue<Integer> pq = new PriorityQueue<>((n1, n2) -> {
			새로운 우선순위를 정의해 준다.  
            
            입력받은 수를 절대값으로 바꾸고 
			int first_num = Math.abs(n1);  
			int second_num = Math.abs(n2);
			
			//절대값이 같으면
			if (first_num == second_num ) {
            
            먼저 입력 받은 수가 뒤에 입력 받은 수보다 크다면 1, 아니라면 -1 
				return n1 > n2 ? 1 : -1; 
			}
			
			//절대 값이 다르다면 
			return first_num - second_num; 
			//이렇게 하게 되면 값이 음수인지 양수인지 판단 하여 
            //숫자를 어디에 배치할 지 알 수 있음
		}); 
		
		for (int i =0; i <N; i ++) {
        
			int r = Integer.parseInt(br.readLine());
			
            if (r == 0) {
				if (pq.isEmpty()) {
					System.out.println("0");
				} else {
					System.out.println(pq.poll());
				}
			} else {
				pq.add(r); 
			}
		}
	
	}

}

 

 

앞선 우선순위 큐의 사용법에 대해 간략하게 올렸지만 Comparator 에는 규칙이 있다. 

[PriorityQueue] 자바의 우선순위 큐 사용법

 

 

 

[Comparator 사용법]

 

비교 할 숫자 두 개 (여기서는 n1, n2). 

우선순위 큐에서 Comparator를 사용하여 숫자를 비교하여 값을 리턴할 때는, 

음수, 0 , 양수 이렇게 세가지를 리턴할 수 있다. 

 

• 음수 리턴 : 첫번째 값(n1)이 두 번째 값 (n2) 보다 앞에 위치한다. 
• 0 리턴 : 두 값이 동등한 우선순위를 가진다
• 양수 리턴 : 두번째 값(n2)이 첫 번째 값보다 앞에 위치한다. 

 

PriorityQueue는 Comparator 가 반환 하는 값의 부호를 기반으로 값을 정렬한다.