[백준] 1931번 : 회의실 배정 – JAVA [자바]

[Silver I] 회의실 배정 - 1931

문제 링크

성능 요약

메모리: 175288 KB, 시간: 1296 ms

분류

그리디 알고리즘, 정렬

문제 설명

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

---

• 문제 풀이

위 문제는 풀었지만 시간 초과로 인해 전략을 바꿔야 했다. 

 

" 회의의 수가 최대가 되려면, 회의가 최대한 빨리 끝나야 한다.

따라서 회의의 끝나는 시간이 빠른 것부터 정렬한다. "

 

1. Time이라는 클래스를 만들어 시작 시간과 끝나는 시간을 받을 수 있게 한다.
2. 회의의 수 N을 입력받고, Time객체를 입력 받아 data 리스트에 넣어준다.
3. Collections.sort(new Comparator) 을 override해서 정렬한다.
   1. 끝나는 시간이 다를 경우, 끝나는 시간을 기준으로 오름차순 정렬
   2. 끝나는 시간이 같을 경우, 시작 시간을 기준으로 오름차순 정렬
4. 0번 idx부터 n-1 idx까지 반복문을 돌면서 다음의 과정을 수행한다.

   <idx : 0> 1 4
   <idx : 1> 3 5
   <idx : 2> 0 6
   <idx : 3> 5 7

    
   1. 위의 데이터가 주어졌을 때, 처음 0번째 시작 값이 0보다 클 경우(default) count를 증가시키고  끝나는 시간은 0번째 끝나는 시간 값인 4로 갱신 된다. (end_time = 4)
   2. 1번째 시작 값인 3이 end_time보다 작으므로 넘어간다. (2번 idx 또한 마찬가지 이유로 넘어간다.)
   3. 3번째 시작 값인 5가 end_time와 같으므로, count는 1 증가하고 end_time은 7로 갱신한다.
   4. 위와 같은 과정으로 n-1 idx까지 수행한다.

---

• 정답 코드

import java.util.*;

class Time{

    int start;
    int end;

    public Time(int s, int e){
        this.start = s;
        this.end = e;
    }
}
public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        List<Time> data = new ArrayList<>();

        for(int i = 0; i < n; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            data.add(new Time(start, end));
        }
        // 끝나는 시간을 기준으로 오름차순 정렬
        // 만약 끝나는 시간이 같다면 시작 시간을 기준으로 오름차순 정렬
        data.sort(new Comparator<Time>() {
            @Override
            public int compare(Time o1, Time o2) {
                if(o1.end == o2.end){
                    return Integer. compare(o1.start, o2.start);
                }else{
                    return Integer.compare(o1.end, o2.end);
                }
            }
        });

        int count = 0;
        int end_time = 0;
        
        for(int i = 0; i < n; i++){
            if(end_time <= data.get(i).start){
                count++;
                end_time = data.get(i).end;
            }
        }
        System.out.println(count);
    }
}

• 시간 초과 코드 (혹시나 해서 올려봅니다.. 피드백 주시면 감사하겠습니다..!)

import java.util.*;

class Time{

    int start;
    int end;

    public Time(int s, int e){
        this.start = s;
        this.end = e;
    }
}
public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        List<Time> data = new ArrayList<>();

        for(int i = 0; i < n; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            data.add(new Time(start, end));
        }
        data.sort(new Comparator<Time>() {
            @Override
            public int compare(Time o1, Time o2) {
                if(o1.end == o2.end){
                    return Integer. compare(o1.start, o2.start);
                }else{
                    return Integer.compare(o1.end, o2.end);
                }
            }
        });
        List<Integer> counts = new ArrayList<>();

        int idx = 0;
        while (idx < n){
            int count = 1;
            for(int i = idx; i < n; i++){
                for(int j = i+1; j < n; j++){
                    if(data.get(i).end <= data.get(j).start){
                        count++;
                        i = j;
                    }
                }
            }
            counts.add(count);
            idx++;
        }
        System.out.println(Collections.max(counts));
    }
}