[Algorithm] 99클럽 코테 스터디 20일차 TIL BOJ 19598

문제

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

풀이

문제 분석

• 주어지는 회의실 사용 시간을 Room 객체로 관리하며, 시작 사용 시간을 기준으로하여 오름차순으로 정렬한다
• for문을 돌면서 우선순위 큐에 끝나는 시간이 빠른 순서대로 회의 예약 정보를 추가한다
  • 이때 현재 검사하는 회의 예약 정보의 시작 시간보다 끝나는 시간이 빠른 회의 예약 정보들을 큐에서 제거한다 (이미 회의실 사용이 끝났기 때문이다)
• answer의 값을 우선순위 큐의 크기로 업데이트하여 주어진 회의실이 최대로 필요한 순간에 대한 정보를 저장한다

코드

import java.io.*;
import java.util.*;

class Room {
    private int start;
    private int end;

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

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        List<Room> rooms = new ArrayList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int answer = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            rooms.add(new Room(start, end));
        }
        
        rooms.sort(Comparator.comparingInt(Room::getStart)
                .thenComparingInt(Room::getEnd));

        for (Room room : rooms) {
            while (!pq.isEmpty() && pq.peek() <= room.getStart()) {
                pq.poll();
            }


            pq.offer(room.getEnd());
            answer = Math.max(answer, pq.size());
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }
}

TIL

• 정렬된 회의실 리스트가 아닌 우선 순위 큐만을 사용하여 현재 끝나는 시간이 제일 빠른 회의 예약 정보와 나머지 회의실들의 시작 시간을 비교하려고했었다. 이 과정에서 큐는 인덱스가 없기 때문에 큐를 다시 리스트로 변환하는 과정을 추가하게 되었고 시간초과가 발생했다
• 두번째로 시도한 방법은 시작 시간을 기준으로 리스트를 정렬해두고 현재 회의실을 사용해야하는 예약 정보만 관리하기 때문에 검사하는 회의 예약 정보와 큐에 존재하는 예약 정보만 확인한다는 점에서 시간적으로 더 효율적이다
• 첫번째 코드는 O(N^2)에 가까운 시간복잡도를 보이지만 정답인 코드는 각 요소를 offer하거나 poll하기 때문에 O(NlogN)의 시간 복잡도를 가지게 된다