[백준] 1931번 회의실배정

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q1931.kt

회의실을 최대한 많이 사용할 수 있는 경우의 수를 출력하여라.
회의실의 끝나는 시간에 바로 다음 강의를 시작할 수 있다.

처음 생각

최대한 많이 회의를 많이 할 수 있는 경우를 따져봐야한다. 최대한 따져보라는 말을 토대로 그리디적인 접근을 해볼 필요가 있다.

▶ 회의를 많이 해야하므로, 끝나는 시간이 빠른 회의먼저 회의를 하면된다.

다음 생각

회의를 끝나는 순서대로 정렬해준 후, 빠른 순서대로 회의장을 사용하도록 하였더니 틀렸습니다가 나왔다. 같은 시간에 끝난 경우를 염두해 두지 않았기 때문이다.

▶ 회의가 같은 시간에 끝날 경우는 시작시간에 빠른 순서대로 넣어준다. 이런순으로 오름차순 정렬을 해주어야 시작 시간과 끝나는 시간이 같은 회의의 처리가 가능하다.

▶ 예를들어 (1 3) (3 3) 이 있다고 볼 때, (3 3)이 먼저 회의를 하면 (1 3)은 처리가 안된다 반대로 (1 3)부터 회의를 시작하면 (3 3)도 회의가 가능하다.

방안

1) Kotlin 풀이( Java 풀이와 비교해보면 짧은것을 확실히 볼 수 있다. 특히, 람다식의 사용과 class의 선언에 있어서 Java와 비교해 무척 짧다)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

package baekjoon.q1000   import java.util.* import kotlin.Comparator   fun main(args:Array<String>){     var sc : Scanner = Scanner(System.`in`)     var n = sc.nextInt()     var arr : Array<Pair> = Array(n,{Pair(0,0) })     for(i in 0..(n-1))         arr[i] = Pair(sc.nextInt(),sc.nextInt())       Arrays.sort(arr, Comparator { o1: Pair, o2: Pair ->         if(o1.e==o2.e) o1.s.compareTo(o2.s)         else o1.e.compareTo(o2.e) })     var result = 1     var end = arr[0].e     for(i in 1..(n-1)){         if(arr[i].s>=end){             result++             end = arr[i].e         }     }     println(result) } class Pair(val s: Int, val e: Int)

2) Java 풀이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

import java.util.Arrays; import java.util.Comparator; import java.util.Scanner;   public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         Pair[] arr = new Pair[n];         for(int i=0;i<n;i++)             arr[i] = new Pair(sc.nextInt(),sc.nextInt());         // 끝나는 시간 순, 끝나는 시간이 같으면 시작 순으로 정렬         Arrays.sort(arr,Pair.comparator);         int result = 1;         int end = arr[0].e;         // 끝나는 시간마다 다음껄 찾아주기         for(int i=1;i<n;i++){             if(arr[i].s>=end){                 end = arr[i].e;                 result++;             }         }         System.out.println(result);     }       static class Pair{         int s,e;         Pair(int s,int e){             this.s = s;             this.e = e;         }         static Comparator<Pair> comparator = new Comparator<Pair>() {             @Override             public int compare(Pair o1, Pair o2) {                 if(o1.e>o2.e) return 1;                 else if(o1.e==o2.e){                     if(o1.s>o2.s) return 1;                     else return -1;                 }else return -1;             }         };     } }