[백준 19580] 마스크가 필요해 - JAVA

BOJ Link

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

 

 

개요

정렬 + 우선순위 큐 + 그리디 문제이다.

 

추가 시간이 없는 문제라 Java로 풀시 까다롭다.

O(M+N+(M+N)log??) 코드로도 시간 초과를 받았다.

이후 sort 2번 + pq 1개 코드에서, pq 3개로 바꿔서 통과했다.

 

풀이 과정

탐색 이전에, 시민을 마스크를 사려는 최소 가격(s)기준 오름차순으로 정렬한다. 이후 마스크를 가격(price)기준 오름차순 정렬한다.

(s가 같다면 최대 가격(e)기준 오름차순 정렬할 필요는 없다.)

 

이후 탐색한다.

이 때, 정렬 후 판매할 수 있는 시민 후보를 담은 우선순위 큐를 별도로 사용해야 하는 이유는 다음과 같다.

 

우선 순위 큐를 사용하지 않을시, 첫번째 시민의 s가 2이므로 먼저 뽑힐 것이고, s가 3인 경우를 뽑아야하는 경우가 반례이다. 따라서, s <= m인 모든 후보 군을 우선순위 큐에 넣고, e가 작은 순서부터 뽑아야 한다. 이는 그리디한 접근임을 의미한다.

 

또한, 우선순위 큐에는 시민의 e만 저장한다.

큐에 넣기전에 i번째 마스크의 price와 s를 비교하고, 마스크는 오름차순 정렬되어 있기에,

항상 i+a번째 마스크의 price는 큐에 있는 원소의 s보다 크거나 같음이 보장된다. 즉, e만 비교하면 범위안임을 알 수 있다.

 

1. price > pq.peek()(=e) 라면,  팔 수 없으므로 pq.poll() 한다. (3번과 이어진다.)

 

2.

price < s 라면 다음 시민으로 넘어간다.

price >= s이고,

price <= e 라면 pq에 넣는다.

price > e라면 다음 시민으로 넘어간다.

 

3. 이후엔 price <= pq.peek()(=e)이고,  stock이 남아있다면 판매한다.

 

제출 코드

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        PriorityQueue<long[]> people = new PriorityQueue<>(Comparator.comparing(o -> o[0]));
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            people.offer(new long[]{Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken())});
        }

        PriorityQueue<long[]> mask = new PriorityQueue<>(Comparator.comparing(o -> o[0]));
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            mask.offer(new long[]{Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken())});
        }

        PriorityQueue<Long> buyer = new PriorityQueue<>();

        int ans = 0;

        for (int i = 0; i < M; i++) {
            long[] nowM = mask.poll();

            long price = nowM[0];
            long stock = nowM[1];

            while (!buyer.isEmpty() && buyer.peek() < nowM[0]) {
                buyer.poll();
            }

            while (!people.isEmpty() && people.peek()[0] <= nowM[0]) {
                if (people.peek()[1] >= price) buyer.offer(people.peek()[1]);
                people.poll();
            }

            while (!buyer.isEmpty() && buyer.peek() >= price && stock != 0) {
                buyer.poll();
                stock--;
                ans++;
            }
        }

        System.out.println(ans);
    }
}