[백준] 11268 - 자바

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

 

이 문제의 기준을 보면 까다롭다. 스택이나, 큐처럼 제일 마지막에 들어온 걸 뺀다거나 먼저 들어온걸 먼저 뺀다거나 하는 기준이 아니라, 절댓값이 가장 작은 수를 빼고, 만약에 절댓값이 같다면 두 수중 실제로 작은 수를 빼는 기준이 까다로운 문제다.

이럴 땐, 우선순위 큐를 활용하면 쉽게 풀 수 있다.

 

기본적으로 우선순위 큐는 큐에 들어가는 순간 오름차순 정렬되어 poll하면 가장 작은 수부터 빠져나간다.

그래서 우리는 우리 절댓값 기준으로 오름차순 정렬인데 절대값이 두 수가 있다면 원래 수에서 오름차순으로 정렬할 수 있도록  Comparator를 통한 커스터마이징이 필요하다.

---

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if(Math.abs(o1) == Math.abs(o2)){
                    return o1-o2;
                }
                return Math.abs(o1) - Math.abs(o2);
            }
        });
        StringBuilder sb = new StringBuilder();

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

        }

        System.out.println(sb);



    }
}

 

PriorityQueue는 내부적으로 compare(o1, o2)의 결과를 기반으로
우선순위가 높은 값을 앞으로 (즉, poll() 시 먼저 나오도록) 정렬한다.

return Math.abs(o1) - Math.abs(o2)는 절댓값이 작은 수가 더 우선되도록,
return o1 - o2는 절댓값이 같을 때 실제값이 더 작은 수가 우선되도록 정렬 기준을 설정했다.

이 Comparator를 통해 우리는 문제에서 요구한 “절댓값이 작은 수 우선, 같다면 작은 수 우선”이라는 기준을 우선순위 큐에 그대로 적용할 수 있다.