[우선순위 큐]백준 11286번

문제

1. 첫번째 입력값으로 연산의 개수 N이 주어진다 (1 <= N <= 100,000)
2. 다음 N개의 줄에는 정수x가 주어진다
3. x값이 0이 아니라면 배열에 x라는 값을 추가하고, x가 0이라면 배열에서 절대값이 가장 작은 값을 출력한다
(단, 절대값이 같을경우 음수를 우선순위로 둔다)

*2초이내 풀이

 

문제분석

• N의 최대 범위가 100,000이므로 O(nlogn)이 가능하다
• 데이터가 새로 삽입될때마다 절대값과 관련된 정렬이 필요하므로 우선순위 큐를 이용하여 문제를 해결
• 주의) 정렬기준은 직접 정의해야함 (절대값에 따른 값이 같은 경우 기준 설정 필요)

 

슈도코드

N(질의 요청개수 입력)
우선순위 큐 설정
for(N만큼 반복){
    요청이 0일때, 비어있으면 0 출력 / 있으면 front 출력 (poll())
    요청이 0이 아닐때, queue에 데이터 추가 (add())
}

 

 

구현

• 우선순위 큐 (정렬 추가)
  • 람다를 이용하여 인라인으로 정의해주는방법도 존재
  • 따로 클래스를 구현하여, 사용 ( QueuePrioritySort() )
• BufferedWriter를 이용하여 한번에 출력

import java.util.PriorityQueue;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;

public class App {
    public static void main(String[] args) throws Exception {
        
        // 람다를 이용하여 compare 오버라이딩
        // PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> {
        //     int first_abs = Math.abs(o1);
        //     int second_abs = Math.abs(o2);

        //     if (first_abs == second_abs){
        //         return o1 > o2 ? 1 : -1;
        //     }else{
        //         return first_abs - second_abs;
        //     }
        // });
        
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bwf = new BufferedWriter(new OutputStreamWriter(System.out));
        int inputCount = Integer.parseInt(bf.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>(new QueuePrioritySort());

        for(int i =0; i< inputCount; i++){
            int currentNum = Integer.parseInt(bf.readLine());

            if(currentNum == 0){
                if(queue.isEmpty()){
                    bwf.write("0\n");
                }else{
                    bwf.write(String.valueOf(queue.poll() + "\n"));
                }
            }else{
                queue.add(currentNum);
            }
        }

        bwf.flush();
        bf.close();
        bwf.close();
        

    }

    public static class QueuePrioritySort implements Comparator<Integer>{
        
        /**
         * 1 : o1이 더 우선순위
         * -1 : o2이 더 우선순위
         * 0 : 같음 => 이걸 커스텀해서 처리해준것
         */
        @Override
        public int compare(Integer o1, Integer o2){
            int first_abs = Math.abs(o1);
            int second_abs = Math.abs(o2);

            if(first_abs == second_abs){
                return o1>o2 ? 1 : -1;
            }else{
                return first_abs - second_abs;
            }
        }
    }
}