[코딩테스트] 백준 1931 자바

백준 1931

백준 1931 문제

해당 문제는 1개의 회의실에서 회의가 겹치지 않게 최대한 많은 회의를 배정해야 한다. 이떄 그리디 알고리즘을 사용할 수 있는데, 현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는 데 유리하다.

그렇기 때문에 종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의실을 적절하게 선택하면 이 문제를 해결할 수 있다.

import java.util.*;

public class Boj1931 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 회의 개수
        int[][] arr = new int[n][2]; // 회의 시간 정보
        int count = 0; // 진행할 수 있는 회의 수
        int end = -1; // 회의의 종료 시간

        // 회의 시간 정보 저장
        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        // 회의 시간 정보 정렬
        Arrays.sort(arr, (s, e) -> {
            if (s[1] == e[1]) { // 종료 시간이 같으면
                return s[0] - e[0]; // 시작 시간 기준 정렬
            }

            return s[1] - e[1]; // 종료 시간 기준으로 정렬
        });

        // 회의 개수만큼 반복
        for (int i = 0; i < n; i++) {
            if (arr[i][0] >= end) { // 현재 회의와 겹치지 않는 다음 회의가 나온 경우
                end = arr[i][1]; // 종료 시간 업데이트
                count++; // 진행할 수 있는 회의 수 증가
            }
        }

        System.out.println(count); // 진행할 수 있는 회의 수 출력
    }
}

풀이

1. 회의 개수를 n에 입력 받아 저장한다.
2. 회의의 시작과 종료 시간을 저장할 수 있는 2차원 배열 arr를 int[n][2]로 생성한다.
3. 진행할 수 있는 회의 수 count를 0으로 초기화한다.
4. 현재 회의 종료 시간 end를 -1로 초기화한다.
5. 회의 수만큼 반복하면서 회의 시간 정보를 arr 배열에 저장한다.
6. Arrays.sort()를 통해 회의 시간 정보를 정렬한다.
   6-1. 회의 종료 시간 기준으로 정렬하되, 종료 시간이 같은 회의일 경우 회의 시작 시간 기준으로 정렬한다.
7. 회의 수 만큼 반복한다.
   7-1. 현재 회의 종료 시간과 겹치지 않는 다음 회의가 나온 경우
   7-2. 종료 시간 end를 업데이트한다.
   7-3. 진행할 수 있는 회의 수 count를 1 증가시킨다.
8. 진행할 수 있는 회의 수 count를 출력한다.