[백준 1931] 회의실 배정

[백준 1931] 회의실 배정

문제 출처 : 링크

그리디 알고리즘에 해당하는 문제다.

즉, 최적의 해를 찾기 위한 알고리즘을 짜야하는데, 반례를 잘 찾아가면서 풀어야 한다.

작년에 풀었던 문제였지만, 다시 풀어봐도 반례를 다 생각하지 못해서 상당히 고생했다ㅠ

가장 많은 회의를 진행할 수 있도록 하려면, 가장 빨리 끝나는 회의를 찾아야 한다는 걸 알아내야 한다. 이런 문제는 그냥 많이 풀어보면서 어느정도 감을 익히는게 제일 좋지 않은가 싶다...

나는 우선 class를 하나 만들어 회의에 대한 시작 시간과 종료 시간을 저장했다.

그리고 각 회의 정보를 하나의 리스트에 저장했고, 회의 종료 시간이 빠른 순으로 보기 위해서 Comparator를 활용해 종료시간 오름차순으로 정렬했다.

(이때 int값을 활용해서 오름차순 하기 위해서는 변수를 Integer로 선언해야했음)

여기서 끝인 줄 알았으나, 아래와 같은 반례를 찾지못해 시간이 좀 걸렸다.

회의가 3번일 때

3 3

2 3

3 3

회의의 시작 시간과 종료 시간이 같을 수도 있기 때문에 3 3이 두번 있으면 둘다 모두 동시에 회의가 가능하다. 따라서 답은 3이 출력돼야 한다.

하지만 그냥 이걸 종료 시간으로 sorting 해버리면, 동시에 진행되는 회의 중 하나가 오름차순으로 제대로 정렬되지 못한 채 짤려버리고 2번만 가능하다고 나왔다. 하나의 조건문이 더 필요했다.

public int compare(Seminar s1, Seminar s2) {
    if(s1.getEnd() != s2.getEnd()){
        return s1.getEnd().compareTo(s2.getEnd());
    }
    else
        return s1.getStart().compareTo(s2.getStart());
}

만약 종료 시간이 같은 회의가 존재한다면, 시작 시간으로 한번더 정렬을 해주면서 해결이 가능했다.

전체 소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
 
class Seminar { // 회의 시작, 끝 저장할 클래스
    Integer start;
    Integer end;
    
    Seminar(Integer start, Integer end) {
        this.start = start;
        this.end = end;
    }
    
    public Integer getStart(){
        return start;
    }
    public Integer getEnd(){
        return end;
    }
 
    /*
    @Override
    public String toString() {
        return "(" + start + ", " + end + ")";
    }
    */
 
}
 
class ArrSort implements Comparator<Seminar>{ // comparator로 끝나는 시간 정렬
 
    @Override
    public int compare(Seminar s1, Seminar s2) {
        if(s1.getEnd() != s2.getEnd()){
            return s1.getEnd().compareTo(s2.getEnd());
        }
        else
            return s1.getStart().compareTo(s2.getStart());
    }
    
}
 
public class Problem1931 {
 
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        ArrayList<Seminar> arr = new ArrayList<Seminar>();
        
        int num = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < num; i++) {
            
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            
            Seminar s = new Seminar(start, end);
            
            arr.add(s);
        }
        
        ArrSort arrSort = new ArrSort();
        Collections.sort(arr, arrSort); // 정렬
        
        
        int chkEnd = arr.get(0).end;
        
        int count = 1; // 회의 수 저장 변수(처음 값 저장하고 시작해서 1로 선언)
        
        for (int i = 1; i < arr.size(); i++) {
            
            int e = arr.get(i).end;
            int s = arr.get(i).start;
            
            if(chkEnd <= s){
                chkEnd = e;
                count++;
            }
        }
        
        System.out.println(count);
    }
 
}