[Java] baekjoon_1931 : 회의실 배정

그리디 알고리즘, 정렬

회의실 배정 : Silver1

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

 

 

이 문제는 그리디 알고리즘을 사용하여 문제를 해결할 수 있다.

그리디 알고리즘은 각 단계에서 지금 당장 가장 좋은 선택을 하는 방법으로 문제를 해결하는 알고리즘이다.

회의실 배정 문제에서는 회의가 끝나는 시간을 기준으로 정렬하여 가장 빨리 끝나는 회의부터 차례대로 배정하여 최대로 회의를 배정하는 것이 최적의 해결 방법이다.

 

 

첫 번째 코드 작성

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int[][] meeting = new int[N][2];

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

        Arrays.sort(meeting, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[1] == b[1]) {
                    return Integer.compare(a[0], b[0]);
                }
                return Integer.compare(a[1], b[1]);
            }
        });

        int endTime = 0; // 회의가 끝나는 시간을 저장하는 변수
        int cnt = 0; // 최대로 회의를 배정할 수 있는 개수를 저장하는 변수
		
        // 회의 배정하기
        for (int i = 0; i < N; i++) {
            if (meeting[i][0] >= endTime) { // 현재 회의의 시작 시간이 이전에 배정된 회의의 끝나는 시간보다 늦거나 같은 경우
                endTime = meeting[i][1]; // 현재 회의를 배정하고 끝나는 시간 업데이트
                cnt++; // 회의 개수 증가
            }
        }

        bw.write(cnt + "\n");
        br.close();
        bw.close();
    }
}

 

ㄴ N개의 줄에 걸쳐 각 회의의 시작 시간과 끝 시간을 입력으로 받아 2차원 배열 meeting에 저장한다.
ㄴ 이 문제에서의 포인트는 Arrays.sort() 메서드를 사용하여 회의를 끝나는 시간을 기준으로 정렬하는 것이다. 특히, 회의가 끝나는 시간이 같은 경우에는 시작 시간을 기준으로 정렬하도록 해야한다.

ㄴ 회의 배정을 위해 endTime 변수를 사용하는데, endTime 변수는 현재까지 배정된 회의의 끝나는 시간을 나타낸다.
ㄴ 각 회의에 대해 시작 시간과 endTime을 비교하여 회의를 배정하도록 한다.

ㄴ 만약 현재 회의의 시작 시간이 endTime보다 늦거나 같다면 해당 회의를 배정하고, endTime을 현재 회의의 끝나는 시간으로 업데이트한다.
ㄴ 최종적으로 배정된 회의의 개수를 출력한다.

 

 

두 번째 코드 작성

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int[][] meeting = new int[N][2];

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

        Arrays.sort(meeting, (a, b) -> {
            if (a[1] == b[1]) {
                return Integer.compare(a[0], b[0]);
            }
            return Integer.compare(a[1], b[1]);
        });

        int endTime = 0; // 회의가 끝나는 시간을 저장하는 변수
        int cnt = 0; // 최대로 회의를 배정할 수 있는 개수를 저장하는 변수
		
        // 회의 배정하기
        for (int i = 0; i < N; i++) {
            if (meeting[i][0] >= endTime) { // 현재 회의의 시작 시간이 이전에 배정된 회의의 끝나는 시간보다 늦거나 같은 경우
                endTime = meeting[i][1]; // 현재 회의를 배정하고 끝나는 시간 업데이트
                cnt++; // 회의 개수 증가
            }
        }

        bw.write(cnt + "\n");
        br.close();
        bw.close();
    }
}

 

ㄴ 정렬하는 부분에서 람다식을 이용하도록 바꿔보았다.

 

 

Comparator 인터페이스를 구현한 익명 클래스를 사용한 비교 방법

Arrays.sort(meeting, new Comparator<int[]>() {
    @Override
    public int compare(int[] a, int[] b) {
        if (a[1] == b[1]) {
            return Integer.compare(a[0], b[0]);
        }
        return Integer.compare(a[1], b[1]);
    }
});

 

=>

람다식을 이용하여 Comparator 인터페이스를 구현하는 방법

Arrays.sort(meeting, (a, b) -> {
    if (a[1] == b[1]) {
        return Integer.compare(a[0], b[0]);
    }
    return Integer.compare(a[1], b[1]);
});

 

 

 

그리디 알고리즘(탐욕 알고리즘, Greedy Algorithm)

그리디 알고리즘은 각 단계에서 가장 최적의 선택을 하여 최종적인 해답을 구하는 알고리즘이다.

이 알고리즘은 현재 상황에서 가장 좋은 선택을 하며, 이 선택들이 전체적으로 최적의 해결책이 되는 경우에 사용한다.

이는 여러 선택이 가능한 상황에서 각 단계에서 가장 최선의 선택을 하여 결과를 도출하는 방식으로 동작한다.

최적 부분 구조 (Optimal Substructure)

전체 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성될 때 적용 가능

 

탐욕 선택 속성 (Greedy Choice Property)

각 단계에서 최적의 선택을 하고, 이 선택이 최종 해답에 대한 최적의 선택인 경우에 적용 가능

그리디 알고리즘은 전체 문제를 한 번에 해결하는 대신에 작은 부분 문제들을 순차적으로 해결해나가는 방식으로 동작한다.

이러한 특성으로 인해 그리디 알고리즘은 문제에 따라서 최적의 해를 보장하지 않을 수 있지만, 많은 문제들에서 그리디 알고리즘이 최적의 해를 제공하거나 근사치에 가까운 해를 제공할 수 있으며, 또한 문제를 해결하는 데 있어서 간단하고 효율적인 방법을 제공할 수 있다.

예를 들어, 동전 거스름돈 문제나 회의실 배정 문제는 그리디 알고리즘을 통해 효과적으로 해결할 수 있는 대표적인 예시이다.