[백준/Java] 1374번 강의실

🔗 문제 링크: https://www.acmicpc.net/problem/1374

🔍 고찰 과정

문제의 예시를 바탕으로 어떻게 하면 5개의 강의실을 배정할 수 있는지 설명하겠습니다. 주어진 강의들을 시간대별로 정리해서 그림으로 정리하면 다음과 같이 나타낼 수 있습니다.

여기에서 같은 강의실을 쓰는 강의 시간들을 같은 색깔로 표현하자면 다음과 같습니다.

그림과 같이 5개의 서로 다른 강의실을 배치하여 강의를 진행할 수가 있습니다. 이 방식은 그리디 방식으로 접근을 할 수가 있는데 다음과 같은 과정을 세울 수가 있습니다.

1. 우선 강의 시작 시간, 끝시간 모두를 서로 합쳐서 빠른 시간순으로 오름차순 정렬을 한다. (만약 강의 시작 시간과 끝시간이 겹치는 경우 강의가 끝나고 같은 강의실에서 바로 다음 강의를 진행해주기 위해 끝시간을 우선으로 한다. )
2. 강의 시작 시간은 곧 강의실 하나가 필요하다는 의미이므로 강의 시작 시간이면 +1을 통해서 강의실을 사용한다는 의미를 부여해준다.
3. 강의 끝 시간은 하나의 강의실에서 강의가 끝났다는 것을 의미하므로 현재 강의실을 쓰지 않는다는 의미인 -1을 부여해준다.
4. 총 시간대를 돌면서 결국 필요한 총 강의실의 개수를 추출해준다.

이 문제와 똑같은 유형의 문제를 프로그래머스에서도 풀었던 적이 있어 자세한 설명을 보고 싶으시면 다음 링크를 참고하시면 됩니다.

 

https://devjuice.tistory.com/9

[프로그래머스/Java] 호텔 대실

 

---

✏️ 코드

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

public class Main {

    private static final int START = 1;
    private static final int END = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int answer = 0;
        List<int[]> times = new ArrayList<>();

        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            int roomNumber = Integer.parseInt(st.nextToken());
            int startTime = Integer.parseInt(st.nextToken());
            int endTime = Integer.parseInt(st.nextToken());

            times.add(new int[]{startTime, START});
            times.add(new int[]{endTime, END});
        }

        times.sort((o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);

        int timeLen = times.size();
        int currentTime = 0;
        for (int i = 0; i < timeLen; ++i) {
            currentTime += times.get(i)[1];

            answer = Math.max(currentTime, answer);
        }

        bw.write(Integer.toString(answer));
        bw.flush();
        bw.close();
    }

}