[014] 1931.회의실 배정

 

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

1931번: 회의실 배정

---

 

진짜 머리 빠개지는 줄 알았음 타임오버 개새끼

 

회의실 사용은 시작시간 / 끝나는 시간이 주어진 상태고, 여기에서 최대로 많은 회의를 진행해야 한다.

그렇다면 여기서 중요한 포인트는

시작시간-끝나는 시간이 작은 것이다. 당연함. 회의 시간이 짧을수록 많은 팀을 우겨넣을 수 있다.

그렇다면 정렬을 할 때 

1. 끝나는 시간을 기준으로

2. 끝나는 시간이 같다면 회의 시간이 적은 것으로 

구현을 하면 되시겠다

 

 

import java.util.*;

public class Main {
	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 = 0;

        for(int i = 0; i < n; i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        Arrays.sort(arr, (int[] fst, int[] snd) -> {
            if(fst[1] == snd[1]){

                return fst[0] - snd[0];
            }else{
                return fst[1] - snd[1];
            }
        });


        do{
            int temp = 0;
            for(int i = 0 ; i < n; i ++){
                if(arr[i][0] >= end){
                    end = arr[i][1];
                    count ++;
                    
                    break;
                }
            }
        }while(end != arr[n-1][1]);
        System.out.println(count);
	}
}

 

 

처음 결과

는 당연히 시간 초과가 떴다. 뻘짓을 391418291232189319나번 정도 하고 나서...

생각해보니 do while이 왜 저기있는지 모르겠다. 아마 풀면서 지우는 걸 까먹은 거 같음 ^^!

그것도 모르고 이리 바꾸고 저리 바꾸고 sort를 지우고 처음 입력받을 때마다 정렬을 수행했다가 아주 별짓을 다했다...

 

다 제대로 풀어놓고 마지막에 정신 놓은 수준 (...!)

 

그리고 나서 제출 

저 while 깨닫는 거 30분 걸렸다(^^)!

 

import java.util.*;

public class Main {
	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 = 0;
        int temp = 0;

        for(int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
            }

        Arrays.sort(arr, 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];
            }
        });

        for(int i = 0; i < n; i ++){
            if(end <= arr[i][0]){
                end = arr[i][1];
                count++;
            }

        }



        System.out.println(count);
	}
}

 

 

나는 Comparator를 사용하는 것보다 람다식을 사용하는 것을 좋아하기 때문에(복잡한 연산이 아니면 람다식이 더 보기 좋으니까!) 람다식으로 변경해서 다시 제출했다.

 

import java.util.*;

public class Main {
	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 = 0;
        int temp = 0;

        for(int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
            }

        Arrays.sort(arr, (int[] fst, int[] snd) -> {
            if(fst[1] == snd[1]){

                return fst[0] - snd[0];
            }else{
                return fst[1] - snd[1];
            }
        });

        for(int i = 0; i < n; i ++){
            if(end <= arr[i][0]){
                end = arr[i][1];
                count++;
            }

        }



        System.out.println(count);
	}
}

 

 

 

위에 있는 것이 람다식을 적용한 것이고

아래에 있는 것이 Comparator를 적용한 것이다.

확실히 람다식을 사용하는 것이 메모리를 조금 더 차지하지만 시간이 줄어드는 것과 코드 길이 자체가 짧아지는 것을 확인 가능하다. (근데 저정도 시간차가 유의미할까...?)