1931 회의실 배정

그리디 알고리즘 / 실1

 

작년 2학기에 컴퓨터알고리즘및실습 수업의 실습에서 비슷한 문제를 풀었던 것 같은데, 기억이 잘 나지 않아 고민하다가 구글링을 통해 아이디어를 얻었다.

 

먼저, (답이 아닌) 나의 접근 방식으로는,

시간이 가장 짧은 것들을 우선적으로 배치 -> 겹치는 것들을 어떻게 처리해야할 지 막힘

시작 시간을 기준으로 오름차순으로 배치하되, 같은 것들 중에서는 끝나는 시간이 가장 빠른 것을 우선 배치 -> 제공된 예시 중 0~6이 있었으므로, 이걸 먼저 배치하면 답이 아님을 알았음

 

저기까진 생각했는데 끝나는 시간만을 기준으로 배치한다는 것은 생각하지 못했다.. 아직 멀었군

 

nx2 행렬을 인덱스 1 값을 기준으로 오름차순으로 정리하는 방법을 자바에서 찾느라 애를 조금 먹었다. 다른 포스팅으로 정리할 예정이다.

이렇게 코드를 작성하여 제출하니까 7 80%정도에서 틀렸습니다가 나왔다.

 

인덱스 1을 기준으로 오름차순으로 정리하되, 인덱스 1값이 같을 경우에는 시작 시간(인덱스 0 값)이 더 작은 것을 우선적으로 배치해야 한다.

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

이것이 nx2 행렬을 인덱스 1을 기준으로 오름차순으로 정리하되, 인덱스 1값이 같을 경우에는 인덱스 0 값을 기준으로 오름차순으로 정렬되도록 만든 코드이다.

 

다음은 전체 코드이다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Comparator;


public class Main {
    private static int n, num = 0;
    private static int [][] array;
    private static int [] last;
    
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        
        n = Integer.parseInt(br.readLine());
        array = new int [n][2];
        last = new int[2];
        for(int i = 0; i < n; i++){
            s = br.readLine();
            StringTokenizer st = new StringTokenizer(s);
            array[i][0] = Integer.parseInt(st.nextToken());
            array[i][1] = Integer.parseInt(st.nextToken());
        }

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

        for(int i = 0; i < n; i++){
            if (last[1] <= array[i][0]){
                last[0] = array[i][0];
                last[1] = array[i][1];
                num++;
            }
        }
        System.out.println(num);
    }
}