[백준] #1931번 회의실 배정 (Java)

백준 1931 - 회의실 배정 바로가기

시작하기 전...

Greedy Algorithm

그리디 알고리즘은 욕심쟁이 알고리즘 이라고도 불리는데, 이름에서 유출할 수 있듯이 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’으로 문제를 해결하는 방법이다.

또한 최적의 값을 구해야하는 상황에서 사용되는 방법론으로, ‘각 단계에서 최적이라고 생각되는 것을 선택’해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.

이때 항상 최적의 값을 보장하는 것이 아니기 때문에 최적의 값의 ‘근사한 값’을 목표로 하고있다.

---

📝 문제 설명

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.
각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.
단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

• 주어진 회의들의 시작 시간 과 종료 시간 을 기준으로, 최대한 많은 회의를 배정할 수 있는 경우를 구하는 문제이다.

입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.
시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

입출력 예시

---

문제 들여다 보기..

• 주어진 조건에 맞춰 최대한 많은 회의를 배정하기 위해 시작 시간과 종료 시간의 관계를 파악 하고, 이를 기준으로 최적의 선택을 반복하는 것이 핵심이다.

• 선택할 수 있는 시간이 많아지려면 서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 회의를 할 수 있다.

(나는 그림을 여러번 그려봤음,...ㅎ)

[그림 최종본임]

위 그림은 ((1,4), (5,7), (8,11), (12,14))가 선택되므로 최대 회의 가능한 수는 4개이다.

❗️포인트❗️
예제 문제는 친절하게도 종료시간을 기준으로 정렬 해줬기 때문에 내 예상시간보다 빨리 풀 수 있었다.

정리하자면 종료시간을 기준으로 정렬해준 다음, 겹치는 부분을 제외하고 남은 회의의 수를 출력하면 된다.

주의
종료 시간이 같은 경우 시작 시간이 빠른 순으로 정렬해야함

---

📌 풀이

	int N = 11;
	int[][] time = {{1,4}, {3,5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}};
------------------------------------------------------------------------------------------------------------------
	/**
	 * 
	 */

	// time 오름차순 정렬 (끝나는 시간을 기준으로 정렬)
	Arrays.sort(time, (o1, o2) -> {
		if (o1[1] == o2[1]) { // 종료 시간이 같을경우 시작시간이 빠른 순서로 정렬시킴
			return o1[0] - o2[0]; // 시작 시간으로 정렬
		}
		return o1[1] - o2[1]; // 종료 시간으로 정렬
	});
    
    // 앞에 회의의 끝나는 시간이 다음 회의의 시작시간과 같거나 작을때 카운트
        for (int i = 0; i < N; i++) {
            if (end <= time[i][0]) {
                // ex) 4 <= 5
                count++;
                end = time[i][1]; // 끝시간 저장해주기
            }
        }
        System.out.println(count);

---

📚 코드 설명

1️⃣ 입력 처리 및 배열 생성
사용자로부터 N 값을 입력받아 처리
N 은 1 ≤ N ≤ 100,000 로 제한
(입출력 예시로 11로 초기화 설정함)

2️⃣ 정렬
Arrays.sort()와 Comparator를 사용해 종료 시간 기준으로 정렬한다.
o2[1]: 종료 시간 기준 오름차순 정렬
동일한 종료 시간이 있다면 o1[0] - o2[0]: 시작 시간이 빠른 순서로 정렬

3️⃣ 회의 배정
현재 종료 시간(end)을 기준으로 다음 회의의 시작 시간을 확인한다.
조건을 만족하면 카운트를 증가시키고, 종료 시간(end) 갱신시킴

---

전체코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // N개의 회의
        int count = 0;
        int end = 0;
        int[][] time = new int[N][2];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine()); // ex) 1 4 저장
            // 시작 시간 저장
            time[i][0] = Integer.parseInt(st.nextToken()); // ex) 1 저장
            // 종료 시간 저장
            time[i][1] = Integer.parseInt(st.nextToken()); // ex) 4 저장
        }

        // time 오름차순 정렬 (끝나는 시간을 기준으로 함)
        Arrays.sort(time, (o1, o2) -> {
            if (o1[1] == o2[1]) { // 종료 시간이 같을경우 시작시간이 빠른 순서로 정렬시킴
                return o1[0] - o2[0]; // 시작 시간으로 정렬
            }
            return o1[1] - o2[1]; // 종료 시간으로 정렬
        });


        // 앞에 회의의 끝나는 시간이 다음 회의의 시작시간과 같거나 작을때 카운트
        for (int i = 0; i < N; i++) {
            if (end <= time[i][0]) {
                // ex) 4 <= 5
                count++;
                end = time[i][1]; // 끝시간 저장해주기
            }
        }
        System.out.println(count);
    }
}

---