[Softeer] 강의실 배정 - Java

https://softeer.ai/practice/result.do?eventIdx=1&submissionSn=SW_PRBL_SBMS_178768&psProblemId=392#hold 

https://softeer.ai/practice/result.do?eventIdx=1&psProblemId=392&submissionSn=SW_PRBL_SBMS_178768#hold

---

1. 문제

수업 개수와 수업 시작시간, 끝 시간이 줄마다 주어진다.

최대한 많은 개수의 수업을 들을 때 수업의 총 개수를 출력한다.

수업시간은 겹칠 수 없으나 시작시간과 끝시간은 동일할 수 있다.

 

2. 풀이

구현 문제이다.

나는 처음에 2가지 풀이방법을 생각했다.

 

첫 번째는 강의시간이 짧은 순서대로 정렬해서 cnt를 늘리는 방법이다.

=> 이렇게 하면 (3,5), (4,6), (1,4) 의 경우 (1,4)(4,6)으로 정답은 2인데 (3,5)가 선택되어 답이 1이게 된다.

그래서 강의시간을 기준으로 정렬하면 안되고 끝시간을 기준으로 정렬해야 한다.

 

두 번째는 DFS 풀이를 생각했다.

=> 하지만 1 ≤ N ≤ 10^6 인 정수 이므로 시간초과가 날 것이므로 좋지 못한 방법이다.

 

결과적으로 해결한 방법은

1. 강의 끝 시간이 빠른 순서대로 정렬하고

2. nowEnd를 0으로 설정하고 시작하여 for문으로 시작시간보다 nowEnd가 작거나 같을 때

 nowEnd를 그 강의의 끝 시간으로 갱신, cnt를 1 늘려준다.

 

요약:

끝 시간이 빠른 순으로 정렬 -> 시작시간과 비교 후 갱신

 

실행시간 1943ms

메모리 79.3Mb

 

3. 코드

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


public class Main
{
    static int N, ans, nowEnd;
    static int[][] lecture;

    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        lecture = new int[N][2];

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

        Arrays.sort(lecture, (o1,o2)->o1[1]-o2[1]);

        for (int i=0; i<N; i++) {
            if (nowEnd <= lecture[i][0]) {
                nowEnd = lecture[i][1];
                ans++;
            }
        }
        System.out.println(ans);
    }
}

 

4. 사담

복잡하게 생각하기 보단 더 효율적이고 좋은 방법을 생각해보자