[백준] 20440. 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

문제 링크

[백준] 20440. 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

풀이 과정

우선순위 큐를 사용해 풀었습니다. 예제를 통해 설명하겠습니다.

위와 같은 모기 정보가 주어집니다. 모기 ①이 먼저 방에 진입한 이후에 모기 ②가 진입해야 비로소 같은 시간대에 두 마리가 공존할 수 있습니다. 또한, 모기 ③은 모기 ①과 ②가 진입한 이후에 들어와야 동시간대에 최대 세 마리가 공존할 수 있습니다. 따라서, 모기가 진입하는 시간에 따라 최대 모기 마릿수가 달라질 수 있기에, 진입 시간을 오름차순 기준으로 정렬해줍니다.

먼저 첫 번째 모기를 우선순위 큐에 넣어줍니다. 이 때, 큐의 사이즈는 1이고, 이는 곧 최대 모기가 1마리임을 의미합니다. 또한, 모기가 가장 많이 있는 시간대는 모기 ①의 시간대, 즉 [2, 16) 이 됩니다.

다음 번 모기가 방 안에 있는 모기들 중 가장 먼저 나가는 모기가 나가기 전에 들어간다면, 방 안 최대 모기 수는 증가하게 됩니다. 현재 방 안에는 한 마리의 모기(모기 ①)가 있으며, 그 모기는 16에 나갑니다. 해당 모기가 나가기 전에 모기 ②가 들어오게 되므로(모기 ②의 입장 : 6 < 모기 ①의 퇴장 : 16) 최대 모기는 2마리가 됩니다. 또한, 최대 모기수가 증가했으므로, 방에 막 들어온 모기의 입장 및 퇴장 시간을 고려해 구간을 설정해줍니다.

방에 있는 모기들 중 가장 먼저 나가는 모기의 퇴장 시간과 다음 번 들어오는 모기의 입장 시간이 방 안 최대 마릿수 를 결정짓습니다. 예를 들어, 현재 방 안에는 3마리의 모기가 있고, 방 안 모기들 중 가장 먼저 나가는 모기(위 그림상 빨간색)의 퇴장 시간이 10, 다음 번 들어오는 모기(위 그림상 파란색)의 입장 시간이 5이면, 모기는 최대 4마리가 존재(시간 5부터 시간10까지)할 수 있습니다. 따라서, 모기의 퇴장 시간 정보를 오름차순으로 가지고 있어야 합니다. 이를 우선순위 큐의 정렬 기준에 대입합니다.

모기 ③은 방 안 가장 먼저 나가는 모기(모기 ②)가 나가기 전에 들어오므로, 최대 3 마리가 존재할 수 있습니다. 모기의 최대수가 변경되었으므로, 가장 많이 공존할 수 있는 시간대를 변경해줍니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        Pair[] pairs = new Pair[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int Te = Integer.parseInt(st.nextToken());
            int Tx = Integer.parseInt(st.nextToken());

            pairs[i] = new Pair(Te, Tx, 1);
        }

        Arrays.sort(pairs, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return Integer.compare(o1.start, o2.start);
            }
        });

        PriorityQueue<Pair> pq = new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return Integer.compare(o1.end, o2.end);
            }
        });

        int maxCnt = 0, Tem = 0, Txm = 0;

        for (Pair p : pairs) {
            while (!pq.isEmpty() && p.start >= pq.peek().end) pq.poll();

            pq.add(p);

            if (pq.size() > maxCnt) {
                maxCnt = pq.size();
                Tem = p.start;
                Txm = pq.peek().end;
            } else if (pq.size() == maxCnt && Txm == p.start) {
                Txm = p.end;
            }
        }

        System.out.println(maxCnt + "\n" + Tem + " " + Txm);
    }

    static class Pair {
        int start, end;

        public Pair(int start, int end, int cnt) {
            this.start = start;
            this.end = end;
        }
    }
}