자바(백준) 14235 크리스마스 선물

오답 노트 & 새로 알게 된 점

처음에 이 문제를 이해하는데 어려웠다.

 

a가 0일 때마다 정렬을 하고 거기서 최대값을 뽑아야한다.

이 때, 시간 복잡도는 N^2log(N)이 예상 되어 TLE가 날 것 같다.

 

그래서 우선순위 큐를 이용하여 정렬하는데 logN을 사용하고 NlogN이 되어 TLE가 안난다.

 

0이면 pq에서 poll하고

0이 아니면 그 개수만큼 pq에 offer하는 것이다.

 

---

코드

package Data_Structure;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class BOJ14235 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N;
    static PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->{
       return o2 - o1;
    });
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        N = atoi(br.readLine());
 
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = atoi(st.nextToken());
 
            if(a == 0){
                if(pq.isEmpty()) sb.append(-1).append("\n");
                else sb.append(pq.poll()).append("\n");
            }
            else{
                for (int j = 0; j < a; j++) {
                    pq.offer(atoi(st.nextToken()));
                }
            }
        }
 
        System.out.print(sb);
    }
}