백준 1379 - 강의실 2

문제

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

리뷰

우선순위큐를 활용하여 강의실 순서를 배치하는 로직은 아래 글을 참고

백준 1374 - 강의실
:https://velog.io/@mj3242/%EB%B0%B1%EC%A4%80-1374-%EA%B0%95%EC%9D%98%EC%8B%A4

강의에 인덱스를 붙여 배정된 강의실 번호와 매핑해주기 위해 Map을 활용하였다.
강의실 문제를 풀이하였던 로직내에서 새로운 강의실이 배정될 때마다 Map에
강의 번호를 key로 하여 강의실 번호를 value로 저장하였다.

이후, 강의 번호를 기준으로 오름차순으로 Map.Entry를 정렬하여 1~N 강의 번호에
따라에 배정된 강의실 번호를 출력하였다.

유의할 점은 주어진 강의 번호의 오름차순에 따라 배정된 강의실 번호를 출력해야 한다는
점이었다. 문제의 출력 조건이 명확치 않아 질문 게시판을 참고하여 해당 조건을
발견했다.

로직의 시간복잡도는 우선순위큐를 활용해 강의별로 강의실 번호를 배정하는 부분에서
$O(NlogN)$으로 수렴하고, 이는 $N=100,000$인 최악의 경우에도 무난히 제한 조건
2초를 통과한다.

코드

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = parseInt(br.readLine());
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Lecture> pq = new PriorityQueue<>(Comparator.comparingInt(l -> l.start));

        StringTokenizer st;
        int num, start, end;
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            num = parseInt(st.nextToken());
            start = parseInt(st.nextToken());
            end = parseInt(st.nextToken());
            map.put(num, -1);

            pq.offer(new Lecture(num, start, end));
        }

        int count = 0;
        PriorityQueue<Lecture> pq2 = new PriorityQueue<>(Comparator.comparingInt(l -> l.end));

        while (!pq.isEmpty()) {
            Lecture l = pq.poll();

            if (pq2.isEmpty()) {
                pq2.offer(l);
                count++;
                map.put(l.idx, count);
                continue;
            }

            if (pq2.peek().end > l.start) {
                count++;
                map.put(l.idx, count);
            } else {
                map.put(l.idx, map.get(pq2.poll().idx));
            }

            pq2.offer(l);
        }

        System.out.println(count);
        List<Map.Entry<Integer, Integer>> collect = new ArrayList<>(map.entrySet());
        collect.sort(Comparator.comparingInt(Map.Entry::getKey));
        for (Map.Entry<Integer, Integer> entry : collect) {
            System.out.println(entry.getValue());
        }
        br.close();
    }


    static class Lecture {
        int idx, start, end;

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

결과