백준 1931 - 회의실 배정 (Java)

 

문제 개요

 

문제 개요

 

예제 입출력

 

---

 

풀이

 

문제에서 원하는 바를 요약하자면 '같은 시간대에 두 개 이상의 회의가 일어나지 않는 조건일 때, 가장 많은 회의를 발생시키려면 몇 개의 회의가 진행될 수 있는지 구하는 프로그램을 작성하라'이다.

 

우선 백준 카테고리에서 그리디 알고리즘으로 검색했기 때문에 처음부터 그리디 방식을 사용해야겠다 라는 생각으로 문제에 접근했다. (아니었다면 조금 더 헤맸을 것 같다.)

 

나는 이 문제를 처음 직면하고 세 가지 정도의 생각을 했다.

 

• 회의 런 타임이 짧은 순서대로 입력받은 회의를 정렬하고 끼워 맞추자.
• 회의 시작 시간을 기준으로 입력받은 회의를 정렬하고 반복문으로 개수를 정하자.
• 회의가 종료되는 시간을 기준으로 입력받은 회의를 정렬하고 반복문으로 개수를 정하자.

 

가장 처음에 했던 런 타임이 짧은 순서로 정렬을 해야 한다면 정렬 자체는 가능하겠지만, 런 타임이 짧은 기준으로 정렬해서 나열했다고 해서 가장 많은 회의를 발생시킨다는 100 퍼센트의 보장은 절대 할 수 없다고 생각했다.

 

물론 그리디 알고리즘을 사용한다면 진정한 답이 출력되지 않을 수 있지만, 왠지 너무 답과 달라질 것 같았다. 예를 들어 런 타임이 짧아서 골라온 회의인데 해당 회의를 제거하고 남은 두 개 이상의 회의를 추가할 수 있다면 벌써 맞는 답이 아니기 때문이다. (반례 존재)

 

두 번째로 시작 시간을 기준으로 정렬하려고 했던 이유는 '각 회의가 겹치지 않도록 정렬할 수 없을까'라는 생각이 밑바탕이 되었기 때문이다. 하지만 예를 들어 첫 회의가 너무 길어서 첫 회의가 아닌 두 번째로 시작되는 회의부터 시작했을 경우 최적의 해가 될 수도 있고, 이런 케이스가 너무 많을 것처럼 생각되었다. (반례 존재)

 

그래서 고민하다가 세 번째인 종료 시간을 기준으로 정렬하는 것을 떠올린 것이다. 종료 시간이 빠른 순으로 정렬한 후 종료 시간이 가장 빠른 회의부터 가장 늦은 회의까지 반복문을 돌린다면 언제 끝날지 모르는 걱정을 할 필요가 없다. 또한 자동으로 회의가 겹치지 않는 케이스를 추출할 수 있다. 

 

그래서 내가 생각한 이번 문제를 해결하는 코드의 작성 순서는 다음과 같다.

 

1. 먼저 2차원 배열 하나를 만들건데, 이는 각각 [입력받은 회의 순서][회의 시작/종료 시간]을 저장할 배열이다.
2. 회의 종료시간을 기준으로 정렬할 건데, 이때 주의할 점이 있다. 당연한 이야기지만 회의 종료시간이 같을 경우 회의 시작시간이 빠른 회의가 우선순위가 된다.
   • 이런 예시가 있을 수 있다. (5, 7) 회의가 있고 (7, 7) 회의가 있을 때 (7, 7) 회의가 먼저 진행된다면 (5, 7)의 회의는 진행될 수 없다. 하지만 반대의 경우엔 두 회의 모두 진행될 수 있다.
3. 정렬이 완료된 후에 한 차례의 반복문을 통해 이전 회의가 끝나는 시간과 다음 회의가 시작되는 시간을 비교하여 겹친다면 그다음 회의를 비교하는 식의 코드를 작성한다.

 

---

 

코드

 

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

public class Main {
    public static void main(String[] arg) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int iCount = Integer.parseInt(br.readLine());
        int[][] cos = new int[iCount][2];

        for (int i=0 ; i<iCount ; i++) {
            String[] items = br.readLine().split(" ");
            cos[i][0] = Integer.parseInt(items[0]);
            cos[i][1] = Integer.parseInt(items[1]);
        }

        Arrays.sort(cos, (o1, o2) -> {
            if (o1[1] == o2[1])
                return o1[0]-o1[1];
            return o1[1] - o2[1];
        });

        int count = 0;
        int lastEnd = 0;
        for (int[] co : cos) {
            if (lastEnd > co[0])
                continue;
            
            lastEnd = co[1];
            count++;
        }

        System.out.println(count);
        return;
    }
}

 

1. iCount에 회의의 총개수를, 2차원 배열 변수인 cos에는 입력받은 각 회의별 시작 시간과 종료 시간을 저장한다.
   • cos[회의 번호][0] : 회의 시작 시간
   • cos[회의 번호][1] : 회의 종료 시간
2. 1 회 전체 루프를 통해 시간을 int로 cos에 저장한다.
3. Arrays.sort() + Comparator를 사용하여 종료 시간을 우선순위로 두고, 종료 시간이 같다면 시작 시간이 빠른 순서대로 정렬한다.
4. 정렬이 완료되면 진행 가능한 회의의 개수(=출력하고자 하는 목표)를 저장할 count와 현재 회의가 종료되는 시간을 의미하는 변수인 lastEnd을 선언한다.
5. 반복문에서 이전 회의의 종료 시간은 lastEnd이고 다음 회의가 시작되는 시간은 co[0]으로, 향상된 for 문으로 진행 가능한 회의의 개수를 구한다.
   • 현재 인덱스의 회의가 시작될 수 있는 상태라면 lastEnd보다 co[0]이 클 것이고, 그렇다면 현재 인덱스의 회의인 co의 종료시간이 lastEnd에 저장 + count를 증가시켜 주는 것이다.

 

---

 

제출 결과

 

채점 결과

 

역시 이전보단 메모리와 시간이 많이 줄긴 했지만 코드 길이는 조금 늘어났다.. 나름 코드 길이를 줄이려고 시도해본 건 비밀은 아니다..^^

 

지금은 효율이 좋아졌으니 상관없지 싶다!!!!