[문제 풀이] 백준 1931번 회의실 배정 JAVA

문제

 

  문제접근 방법   

해당 문제는 회의실 사용표를 작성하는 문제로 회의 수 N개와 각각의 회의 시작시간 ,종료시간을 입력받으면  

중복되지 않고 최대로 사용할 수 있는 개수가 몇개인지 출력하면 되는 문제이다.

처음에는 어떤 방법으로 접근할지 고민이 많았다. 여기서 최대로 사용하려면 회의 시간이 짧은 타임을 여러개 선택해서 

사용표를 작성해야한다는 생각이 들어 그리디 알고리즘을 활용해 최대한 회의 시간이 작은 타임을 여러개 선택하는 방식을 구현해보기로 하였다.

< 초기 코드  >

import java.util.*;

class Reservation{
    int startT;
    int endT;
    int lenT;
    Reservation(int startT,int endT,int lenT){
        this.startT=startT;
        this.endT=endT;
        this.lenT=lenT;
    }
}
public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        Set<Integer> set=new HashSet<>();
        int n=s.nextInt();
        Reservation[] r=new Reservation[n];
        
        int count=0;
        for(int i=0;i<n;i++){
            int startT=s.nextInt();
            int endT=s.nextInt();
            r[i]=new Reservation(startT,endT,endT-startT);
        }
        Arrays.sort(r,(a,b)->a.lenT-b.lenT);
        for(int i=0;i<n;i++){
            int cnt=1;
            for(int t=r[i].startT;t<=r[i].endT;t++){
                int size=set.size();
                set.add(t);
                if(set.size()==size){cnt=0;break;}
                
            }
            if(cnt==1){count++;}
        }
        //System.out.println(set);
        System.out.print(count+1);
    }
    
}

위에서 언급하였듯이 시작시간,종료시간, 회의 시간을 별도의 클래스로 선언하여 관리해주고 이를 배열로 선언 그리고 회의 시간이 짧 값들 먼저 선택해주어야하기 때문에 회의 시간 기준으로 오름차순 정렬을 진행해주었다. 이후 set에 회의 시간이 짧은 것부터

시작시간 ~종료시간까지의 모든 수를 넣어주고 중복이 있으면 count를 안하는 식으로 진행하려했다. 

하지만 중복을 처리하는 과정에서 add해주고 remove를 해줘야하는데 그럼 별도의  set이던지 배열이 또 필요하고 

그렇게 작성한다하더라도 코드가 잘 돌아갈지는 의문이었다. 그래서 정렬을 기준을 길이로 두고 별도의 중복처리 과정을 거치는것이 아니라 종료시간을 오름차순해 종료시간이 짧은것부터 순서대로 넣어주면 별도의 중복처리 없이 코드 구현이 가능할것이라 판단

아래와 같이 코드를 작성하였다.

< 수정 코드 >

import java.util.*;

class Reservation{
    int startT;
    int endT;

    Reservation(int startT,int endT){
        this.startT=startT;
        this.endT=endT;

    }
}
public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);

        int n=s.nextInt();
        Reservation[] r=new Reservation[n];
        
        int count=1;
        for(int i=0;i<n;i++){
            int startT=s.nextInt();
            int endT=s.nextInt();
            r[i]=new Reservation(startT,endT);
        }
        Arrays.sort(r,(a,b)->a.endT-b.endT);
        int select=r[0].endT;
        for(int i=1;i<n;i++){
            if(select<=r[i].startT){
                count++;
                select=r[i].endT;
            }

        }

        System.out.print(count);
    }
    
}

수정한 코드는 위에서 설명하였듯이 정렬기준을 회의 시간이 아니라 종료시간으로 정렬해 별도의 중복처리 과정을 작성하지 않아되게 구현하였다. 하지만 해당 코드는 틀렸다는결과를 받았고 100퍼센트 중  85퍼센트에서 틀렸다는 결과가 나왔다. 

물론 코드 자체가 틀렸을 수도 있지만 보통 85퍼센트 정도까지 올라갔다면 조건의 일부를 구현하지 않은것이라고 생각한다.

그래서 문제를 읽던중 회의 시작 시간과 종료 시간이 같을 수 있다가 눈에 들어왔다. 

예를 들어 1,2 / 2,2 / 2,3 이렇게 존재한다고했을때 종료 시간기준으로만 정렬했기때문에 1,2 /2,2 /2,3 으로 정렬될 수도

2,2/ 1,2/ 2,3으로 정렬될 수도 있다. 해당 코드에서는 가장 앞에 정렬된 값을 먼저 선택하는 흐름이기 때문에 

첫번째는 최대 3개 2번째는 최대 2개로 답이 갈릴수 있다. 그래서 종료시간이 같다면 시작시간을 오름차순으로 정렬해 이를 해결하기로 하였다. 

< 최종 코드 >

import java.util.*;

class Reservation{
    int startT;
    int endT;

    Reservation(int startT,int endT){
        this.startT=startT;
        this.endT=endT;

    }
}
public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);

        int n=s.nextInt();
        Reservation[] r=new Reservation[n];
        
        int count=1;
        for(int i=0;i<n;i++){
            int startT=s.nextInt();
            int endT=s.nextInt();
            r[i]=new Reservation(startT,endT);
        }
        Arrays.sort(r,(a,b)->{
        if(a.endT!=b.endT)return a.endT-b.endT;
        return a.startT-b.startT;}
        );
        
        int select=r[0].endT;
        for(int i=1;i<n;i++){
            if(select<=r[i].startT){
                count++;
                select=r[i].endT;
            }

        }

        System.out.print(count);
    }
    
}

다른 부분은 같기때문에 같으면 다른것을 기준으로 정렬하는 방법만 소개하고 넘어가도록하겠다.

Arrays.sort(r,(a,b)->{
                   if(a.endT!=b.endT) return a.endT-b.endT;
                   return a.startT-b.startT;
} );

위의 코드를 설명하면 아래와 같다.

r을 정렬한다. 그런데 a.endT와 b.endT가 같지 않다면 endT  기준으로 오름차순으로 정렬하고

같다면 startT 기준으로 오름차순 정렬한다.라는 뜻이다.

 

  마무리  

해당 코드는 그리디를 써야한다는 것은 알고 있었으나 최적의 해를 잘못구해 시간이 오래걸린 문제이다.

아직 그리디에 대해서 더 많은 문제를 풀어보고 공부해야겠다는 결심을 했다.

 

 

 참고 자료 

• Comparator