[백준 1374] 강의실 - JAVA

문제

접근 방법

어제 포스팅한 그리디 유형 정리 덕분에
문제를 보자마자 어떤 문제인지 명확하게 파악할 수 있었습니다.

이 문제에서는 강의 시간이 겹친다면
새로운 강의실을 사용해야되는데
즉, 강의 시간이 중첩되는 수만큼 강의실을 열어야 됩니다.

그렇기 때문에 해당 문제는 최대 중첩 유형입니다.
이 문제는 강의실이 어떤 강의실인지 알아야 할 필요가 없고
이벤트 단위로 시작과 종료 이벤트로 나누어서 문제를 풀면
간단하게 문제를 해결할 수 있습니다.

핵심 로직

이벤트를 시작과 종료로 나누고 정렬합니다.

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

Arrays.sort(S);
Arrays.sort(E);

그 다음 스위핑을 통해
종료 이벤트와 비교해 중첩 수를 증가시키거나 감소시킵니다.

int max = 0;
int stack = 0;
int s = 0;
int e = 0;
while (s < N) {
    if (S[s] < E[e]) {
        stack++;
        max = Math.max(max, stack);
        s++;
    }
    else {
        stack--;
        e++;
    }
}

증가시킬 때 최댓값 갱신 로직을 통해
원하는 최대 중접을 구할 수 있습니다.

코드

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


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

        int[] S = new int[N];
        int[] E = new int[N];

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

        Arrays.sort(S);
        Arrays.sort(E);

        int max = 0;
        int stack = 0;
        int s = 0;
        int e = 0;
        while (s < N) {
            if (S[s] < E[e]) {
                stack++;
                max = Math.max(max, stack);
                s++;
            }
            else {
                stack--;
                e++;
            }
        }

        System.out.println(max);
    }
}