자바(백준) 1931 회의실 배정

오답 노트 & 새로 알게 된 점

자바 Collections에 대해 공부를 한 적이 있는데, 이 부분을 지금 알아서 놀랬다.

 

ArrayList를 Integer에 대해 선언하고, Collections.sort를 사용하면 그냥 오름차순이 정렬된다. 그래서 나는 제네릭 부분에 클래스형으로 선언하고 sort를 사용해도 오름차순 정렬될 줄 알았다.

 

그러나 오개념이었다.

 

클래스형을 제네릭으로 ArrayList를 선언하고, Collections.sort를 사용하게 되면 컴파일 에러가 뜬다. 그래서 해당 클래스는 Comparable이나 Comparator 인터페이스를 구현하여 해당 메소드를 오버라이딩 해줘야한다. 

 

그러면 문제로 넘어가보자.

 

이 문제를 읽자마자 최대한 회의를 많이 진행하기 위해서는 회의가 가장 짧은 시간으로만 구성하고, 시작도 가장 빨리해야 한다고 생각했다. 그래서 시작 시간을 오름차순으로 정렬하고, 만약 시작 시간이 같은 경우에는 마무리 시간을 오름차순으로 정렬했다. 그리고 처음부터 맨 마지막까지 선택했을 때, 모든 경우의 수 중 최댓값을 구하려 했다.

 

그러나 시간 복잡도에 의해 TLE가 떴다. 그래서 어떤 방법이 있는지 생각해보았다. 시간 복잡도를 줄이기 위해서는 절대 O(N^2)로 가면 안 되고, for문 하나로 해결해야 할 것 같았다.

 

그래서 마무리 시간을 오름차순으로 정하고, 마무리 시간이 같을 경우 시작 시간을 오름차순으로 정렬하였다. 

 

for문

만약에 다음에 진행할 회의 시간이 현재 마무리 시간보다 작으면 continue를 해준다.

아니면 다음에 진행할 회의 시간이 현재 마무리 시간보다 크거나 같으면 다음 회의로 지정하고, count를 늘려준다.

---

 

코드

import java.util.*;
import java.io.*;
 
public class Main{
    static ArrayList<MeetingPoint> al = new ArrayList<>();
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int num = atoi(st.nextToken());
        for(int i = 0; i < num; i++){
            st = new StringTokenizer(br.readLine());
            int s1 = atoi(st.nextToken());
            int s2 = atoi(st.nextToken());
            al.add(new MeetingPoint(s1, s2));
        }
        Collections.sort(al);
 
        int result = 0;
        int count = 1;
        int end = al.get(0).end;
        for(int i = 1; i < al.size(); i++){
            if(al.get(i).start < end) continue;
 
            else{
                end = al.get(i).end;
                count++;
            }
        }
        System.out.println(count);
    }
    static int atoi(String str){
        return Integer.parseInt(str);
    }
 
}
 
class MeetingPoint  implements Comparable<MeetingPoint>{
    int start, end;
 
    MeetingPoint(int x, int y){
        start = x;
        end = y;
    }
 
    @Override
    public int compareTo(MeetingPoint o) {
        if(this.end - o.end == 0){
            return this.start - o.start;
        }
        else
            return this.end - o.end;
    }
}