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

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

20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

 

---

풀이방법

회의실배정, 강의실배정.. 이 생각났던 문제

 

1. 모기의 시작시간, 끝 시간을 입력받고 오름차순으로 정렬한다.

2. 우선순위 큐에 첫 모기의 끝 시간을 넣고 진행

3. 모기 배열을 순회하면서 우선순위 큐의 제일 작은 값이 모기 시작시간 보다 작다면 큐에서 빼준다.

4. 우선순위 큐의 제일 작은 값이 모기 시작시간과 같다면 큐에서 빼주는데, 그 전에 끝 지점을 바꿔준다.

5. 현재 모기의 끝나는 시간을 넣는다.

6. 우선순위 큐의 크기가 현재 count 보다 크다면 결과값을 갱신해준다.

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] mos;
    static int count, resultS, resultE;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        mos = new int[N][2];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            mos[i][0] = start;
            mos[i][1] = end;
        }

        //정렬 -> 오름차순
        Arrays.sort(mos,(a,b) -> {
            if(a[0] == b[0]) {
                return a[1] - b[1];
            }else {
                return a[0] - b[0];
            }
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(mos[0][1]);
        count = 1;
        resultS = mos[0][0];
        resultE = mos[0][1];

        for (int i = 1; i < N; i++) {
            while(!pq.isEmpty() && pq.peek() < mos[i][0]) {
                pq.poll();
            }
            if(!pq.isEmpty() && pq.peek() == mos[i][0]) { //끝나는 부분이 같으면 pq에서 빼준다.
                if(pq.peek() == resultE) {
                    resultE = mos[i][1];
                }
                pq.poll();
            }

            pq.add(mos[i][1]);
            if(pq.size() > count) {
                count = pq.size();
                resultS = mos[i][0];
                resultE = pq.peek();
            }
        }

        System.out.println(count);
        System.out.println(resultS + " "+ resultE);
    }
}

 

 

결과