[백준] 1931 회의실 배정 (JAVA)

풀이

 처음에는 bfs, dfs문제인줄 알고 덤볐으나 bfs,dfs로는 답이 도출되지 않아서 이리저리 고민하다가 시간별로 정렬하자는 생각이 들었다. 처음에는 사전식으로 정렬하듯이 시작시간먼저 정렬하고 시작시간이 같다면 끝나는 시간으로 정렬하였다. 하지만 이렇게 풀다보니 나중에 값을 도출하는데 시간도 오래 걸리고 복잡하였다. 무엇보다 BOJ에서 시간초과가 나와서 조금더 단순하게 생각기로 했다.

 

 아래 코드는 시작하는 시간순으로 정렬하는것이 아닌 끝나는 시간을 기준으로 정렬하였다. 그리고 만약 끝나는 시간이 같다면  시작하는 시간순으로 정렬하였다. 코드의 중요 포인트는 "이전 회의 기준"으로 끝나는 시각과 다음에 올 적절한 회의를 찾는것이다. 회의시간은 이미 위에서 정렬했기에 차례대로 순회하면 되기때문에 코드는 간단하다.

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

public class Main {

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), "");
        int N = Integer.parseInt(st.nextToken());
        int [][]time = new int[N][2];

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

        Arrays.sort(time, 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 count = 0;
        int prev_end_time=0;
        for(int i=0; i<N; i++){
            if(prev_end_time<=time[i][0]) {
                count++;
                prev_end_time = time[i][1];
            }
        }

        System.out.println(count);

    }
}

 

뭔가 점점 알고리즘 문제들에 대해서 감이 오는것 같다.