백준 11286: 절댓값 힙(java)

문제

---

풀이

 

작은 수부터 출력해야 하므로 최소 우선순위 큐로 풀이하되, 절댓값은 같지만 부호가 다를 경우 순서를 조정해야 하므로 Comparator를 수정한다.

class NewComparator implements Comparator<Integer>{
	@Override
	public int compare(Integer o1, Integer o2) {
		if(Math.abs(o1)>Math.abs(o2)) {
        	//o1의 절댓값이 더 크면 자리 변경
			return Math.abs(o1)-Math.abs(o2);
		}
		else if(Math.abs(o1)==Math.abs(o2)) {
        	//절댓값이 동일하면 음수를 앞으로 보냄
			return o1-o2;
		}
		else {
			return -1;
		}
	}
}

 

이후 11279번 문제와 동일하게 풀이하면 된다.

 

전체 코드

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

class NewComparator implements 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;
		}
	}
}

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Integer> queue=new PriorityQueue<>(new NewComparator());
		StringBuilder sb=new StringBuilder();
		
		int N=Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			int n=Integer.parseInt(br.readLine());
			
			if(n==0) {
				if(queue.isEmpty()) {
					sb.append(0).append("\n");
				}
				else {
					sb.append(queue.poll()).append("\n");
				}
				
				continue;
			}
			
			queue.add(n);
		}
		
		System.out.println(sb);
	}
}