[백준] BOJ 1931 회의실 배정

문제 링크

문제 해석

문제

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

입력

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

출력

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

문제 풀이

무식하게 풀 수 있을까?

무식하게 풀기 - 회의실 사용 가능한 모든 경우의 수 중 가장 많은 경우를 출력한다.
회의 수가 10만이나 입력되기 때문에 아마 모든 경우를 구하기는 메모리제한이 있어서 어려울 것 같다.,

💰그리디 알고리즘 이용

💰 그리디 알고리즘이란?
답을 여러 조각으로 쪼개고, 각 단계마다 지금 당장 가장 좋은 방법만을 선택하는 알고리즘

많은 경우 해를 찾아낼 수 없음, 제한된 경우에서만 사용된다.

그럼에도 그리디 알고리즘을 사용하는 이유?
동적 계획법이나 완전 탐색법보다 훨씬 빠르기 때문에!
속도가 빨라서 그냥 이거 쓸 수 있으면 쓰는게 좋다..

그리디 알고리즘 사용되는 경우

1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우 

2. 시간이나 공간적 제약으로 인해 최적해를 찾기 너무 어려우면 그냥 대충 탐욕법으로 괜찮은 답을 찾음

✨ 그리디 알고리즘의 정당성 증명

탐욕적인 알고리즘이 항상 최적해를 찾아낼 수 있다는 것을 아래 두가지 속성을 증명함으로써 보일 수 있다!

1. 탐욕적 선택 속성

각 단계에서 탐욕적으로 내리는 선택이 항상 최적해로 가는 길 중 하나이며,
탐욕적 선택이 손해가 없다!를 증명

가장 종료 시간이 빠른 회의를 포함하는 최적해가 반드시 존재한다.

• 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 불가능해지는 경우는 없음!

2. 최적 부분 구조

• 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 증명
  대개 자명해서 따로 증명할 필요가 없음!

그리디 알고리즘을 이용한 풀이 구성

구상하기

회의실 배정이 가장 많은 경우는 회의시간이 짧은 회의부터 착착 배정하면 가장 많은 회의를 찾을 수 있을 것 같음

1. 제일 가까운 시간이면서

2. 회의시간이 짧은 회의

따라서, 가장 가까운 시간에 시작하는 회의 중 끝나는 시간이 제일 빠른 회의를 선택!
시간만으로 회의실을 배정하는 경우는 아래처럼 되어 해답을 찾을 수 없다.

• 짧은 하나의 회의를 긴 두회의 대신 잡아버림,,
• 그럴듯하다고 해서 정답이 아니라 쓰기가 까다로움.. 0.ㅠ 항상 정당성 증명이 필요하다!

구현하기

✨ 한 회의를 선택할 때마다 겹치는 회의 모두 제거하는 방법

1. 모든 회의를 종료시간 오름차순으로 정렬
2. 정렬된 회의를 순회하면서 앞 회의와 겹치지 않는 회의 찾기

💡 오름차순 정렬 - Java Arrays.sort 고치기!

sort 방식 커스텀하는 방법은 크게 두가지!

1. Comparable 을 class에 implememt 한 후, compateTo 메소드를 override

2. sort내부에서 comparator를 사용하고, compare메소드를 override

나는 2번이 편해서 2번을 선택해서 풀이를 진행했다.

Comparator 정의

• 정렬 가능한 클래스들의 기본 정렬 기준과 다르게 정렬하고 싶을 때 사용하는 인터페이스

• package: java.util.Comparator

• 주로 익명 클래스로 사용됨

• 기본 정렬 방법인 오름차순 정렬을 내림차순으로 정렬할 때 많이 사용

Comparator 구현 방법

1. comparator interface를 implements

2. compare() 메서드 오버라이드 한 myComparator class 작성

   --> 익명 클래스로도 작성 가능, 아래 코드에서는 익명 클래스로 작성하였음

compare() 메소드 작성법

1. 첫번째 파라미터로 넘어온 객체 < 두번째 파라미터로 넘어온 객체: 음수 리턴

2. 첫번째 파라미터로 넘어온 객체 == 두번째 파라미터로 넘어온 객체: 0리턴

3. 첫번째 파라미터로 넘어온 객체 > 두번째 파라미터로 넘어온 객체: 양수 리턴

✨ 음수 또는 0이면 객체 자리 유지되며, 양수인 경우 두 객체의 자리가 변경된다.

	Arrays.sort(timetable, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                }

                return o1[1] - o2[1];
            }
        });

• o1[1]==o2[1] : 두개 끝나는 시간이 같을 경우

• return o1[0] - o2[0]
  1) o1의 시작하는 시간이 더 빠르면 음수 --> 둘의 위치 바뀌지 않음,
  2) o1의 시작하는 시간이 더 크면 양수 --> 둘의 위치 바뀜 
  --> 더 시작시간이 빠른 게 앞으로 정렬됨

• return o1[1] - o2[1]
  두개 끝나는 시간 비교해서 o1이 더 빨리 끝날 경우 자리 변경 없고, 더 늦게 끝날 경우 o2와 자리 바뀜

문제 풀이 코드

package Greedy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class BOJ1931 {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        int[][] timetable = new int[N][2];
        for (int i = 0; i < N; i++) {
            timetable[i][0] = s.nextInt();
            timetable[i][1] = s.nextInt();
        }

        //timetable 정렬 다시 정의
        Arrays.sort(timetable, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                }

                return o1[1] - o2[1];
            }
        });

        int result = 0;
        int end_time = 0;
        for (int i = 0; i < N; i++) {
            if (timetable[i][0] >= end_time) {
                end_time = timetable[i][1];
                result++;
            }
        }
        System.out.println(result);


    }
}