[ Baekjoon - 10/23 ] - 1931번: 회의실 배정

• 문제 링크 : https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

• 소요 시간 : 1시간 - 그리디와, 자바의 정렬방법이 익숙치 않아 생각보다 시간을 썼던 문제이다.

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 128MB
   • 문제
     
     • 회의의 수 N개(1≤N≤100,000), N개의 시작시간과 종료시간(0≤N≤2^31-1) 
     • 회의가 같은 시간에 진행 될 수 없을 때, 최대 몇개의 회의를 진행할 수 있는지 출력하는 문제
   • 이해
     • 문제를 보자마자 그리디의 전형이라 생각했고, 어떻게 그리디를 구현해야할지 고민해보았다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 문제 이해에 어려움은 없어 생략했다.
3. 문제를 어떻게 해결할 것인가
   • 문제를 읽으며 그리디 문제라 생각했고, 다른 유형은 떠오르지 않았다.
   • 1st 접근 - 시작시간을 기준으로 오름차순으로 정렬하여 규칙을 찾아보자)
     • 그리디를 얇게 공부했던 터라 일단 정렬을 해야한다는 것만 알아서, 시작시간을 기준으로 오름차순, 같으면 종료시간 오름차순으로 정렬해야한다 생각했다.

     • 

     • 우선 눈으로 답이될 회의를 체크한 뒤에 어떤 규칙성이 있는지 생각해보았다. 하지만 생각보다 난해했고, 통일된 규칙을 찾기가 어려웠다..
   • 2nd 접근 - 종료시간을 기준으로 오름차순 정렬을 하여 규칙을 찾아보자)
     • 시작시간을 정렬해서 찾기 힘들다면, 반대로 종료시간을 기준으로 정렬하면 되지 않을까 싶어 해보았다.

     • 

     • 종료시간을 기준으로 앞과 비교해보니
       앞 케이스와 기간이 겹치는데 지금 기간이 짧다면 교체하고, 
       앞 케이스와 기간이 겹치지 않으면 후의 기간을 추가하는 방식으로 하면 구해졌다!
     • 그리고 이 문제는 개수를 구하는 문제이므로 cnt변수를 갱신하는 방향으로 구할 수 있었다.
4. 위 계획을 검증
   • 규칙을 찾기위해 케이스별로 나눠 따져본 것이므로 이미 검증이라 볼 수 있다. 
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main{
            static int N,cnt;
            static int preEndTime;
            static List<Duration> durations;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
                N = Integer.parseInt(br.readLine());
        
                durations = new ArrayList<>();
                for (int n = 0; n < N; n++) {
                    StringTokenizer st = new StringTokenizer(br.readLine());
                    durations.add(new Duration(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
                }
        
                Collections.sort(durations);
        
                for(int i = 0; i < N; i++) {
                    if(preEndTime <= durations.get(i).start) {
                        preEndTime = durations.get(i).end;
                        cnt++;
                    }
                }
                System.out.println(cnt);
            }
        }
        
        class Duration implements Comparable<Duration>{
            int start;
            int end;
        
            public Duration(int start, int end) {
                this.start = start;
                this.end = end;
            }
        
            @Override
            public int compareTo(Duration o) {
                if(end > o.end){
                    return 1;
                }else if((end == o.end)&&(start > o.start)){
                    return 1;
                }
                return -1;
            }
        
            @Override
            public String toString() {
                return "Duration{" +
                        "start=" + start +
                        ", end=" + end +
                        '}';
            }
        }

 

• 결과

IllegalArgument 에러가 발생한 이유는 자바에서 정렬을 하기위해 class에 compareTo메소드를 이용해 정렬 기준을 세워주었지만, 이때 제대로된 조건이 아니어서 오류를 발생시켰다.

위 부분이 잘못된 것이었는데, 좀더 분석해보고 이는 새 게시물에 정리를 하려한다.

 

후에 틀렸습니다 또한, 정렬조건을 이상하게 주어 테케에 어긋난 경우였다.

 

결국 아래와 같이 코드를 바꾸어 제출하였더니 맞았습니다를 얻을 수 있었다.

지금 추측하기로는.. end가 같고 start가 다를때라는 조건을 안주고 단지, start가 다를때만 주어서 틀린것 같기도하다.

아직 제대로 개념이 잡혀있지 않아 후에 꼭 게시물로 작성 할 예정이다...ㅎㅎ