[인프런/Greedy/2. 회의실 배정]

<<풀이>>

 

일단 첫번째 나의 풀이는 그리디를 적용하고, DFS 방식을 이용해서 풀었다.

 

정렬을 하면 끝난 뒷시간과 시작할 앞 시간과 비교하면 되기 때문에 정렬을 했고

 

1, 4 가 처음에 주어지면 다음 4 보다 같거나 큰 것을 찾기 위해 DFS를 이용했다. 

 

그리고 앞시간과 뒷시간이 같으면 무한루프에 빠질 수 있으므로, 한 번 이용한 앞시간은 이용했다는 의미로 ch[앞시간] = 1; 을 해줬다.

 

그렇게 해서 예제문제와 예제정답은 맞출 수 있었다.

 

하지만 최종적인 결과는 시간초과가 났다.

 

내가 생각한 원인은 뒷 시간과 앞 시간을 비교할 때 다시 처음 부터 한 바퀴 돌기 때문이라고 생각했다.

import java.util.Arrays;
import java.util.Scanner;


class Data implements Comparable<Data>{
        int a;
        int b;
        public Data(int a, int b) {
                this.a = a;
                this.b = b;
        }

        @Override
        public int compareTo(Data o) {
                return this.a - o.a;
        }
}

class Main {
        static int answer = 0;
        static int[] ch;
        private void DFS(int n, Data[] data, int b, int count) {
                for (int i = 0; i < n; i++) {
                        if (ch[data[i].a] != 1 && b <= data[i].a) {
                                ch[data[i].a] = 1;
                                count++;
                                DFS(n, data, data[i].b, count);
                                ch[data[i].a] = 0;
                                return;
                        }

                }
                answer = Math.max(answer, count);
        }

        private int solution(int n, Data[] data) {
                int count = 1;
                for (int i = 0; i < n; i++) {

                        DFS(n, data, data[i].b, count);

                }
                return answer;
        }



        public static void main(String[] args) {
                Main T = new Main();
                Scanner in = new Scanner(System.in);
                int n = in.nextInt();
                ch = new int[n + 1];
                Data[] data = new Data[n];
                for(int i = 0; i < n; i++) {
                        data[i] = new Data(in.nextInt(), in.nextInt());
                }

                Arrays.sort(data);

                System.out.println(T.solution(n, data));
        }
}

 

-2번째 풀이-

 

그래서 이번에는 ch를 이용 안 하고 대신 그 다음 인덱스부터 시작할 수 있도록 DFS 에 전의 인덱스를 넣어주고 그 인덱스 + 1를 해줌으로써 처음 부터 도는 형태를 막아줬다.

 

이 역시 예제 풀이는 맞았지만!!

 

최종적으로 오답이 났다 ㅋㅋ

import java.util.Arrays;
import java.util.Scanner;


class Data implements Comparable<Data>{
        int a;
        int b;
        public Data(int a, int b) {
                this.a = a;
                this.b = b;
        }

        @Override
        public int compareTo(Data o) {
                return this.a - o.a;
        }
}

class Main {
        static int answer = 0;

        private void DFS(int j, int n, Data[] data, int b, int count) {
                for (int i = j+1; i < n; i++) {
                        if ( b <= data[i].a) {

                                count++;
                                DFS(i, n, data, data[i].b, count);

                                return;
                        }

                }
                answer = Math.max(answer, count);
        }

        private int solution(int n, Data[] data) {
                int count = 1;
                for (int i = 0; i < n; i++) {

                        DFS(i, n, data, data[i].b, count);

                }
                return answer;
        }



        public static void main(String[] args) {
                Main T = new Main();
                Scanner in = new Scanner(System.in);
                int n = in.nextInt();

                Data[] data = new Data[n];
                for(int i = 0; i < n; i++) {
                        data[i] = new Data(in.nextInt(), in.nextInt());
                }

                Arrays.sort(data);

                System.out.println(T.solution(n, data));
        }
}

 

-강사님 풀이-

 

ㅋ ㅋ

 ㅋ

 ㅋ

ㅋ 

ㅋ  ㅋ

ㅋ ㅋ

ㅋ 진짜.. 간단하게 푸셨다 ㅎㅎㅎㅎ

 

일단 정렬하는 부분에서 나의 생각에 오류가 있었던 것 같다... ㅠㅠ

 

마지막 시간을 기준으로 정렬을 하고 그 다음 시작 시간을 정렬하는 순서이다.. (나는 반대로 했다)

 

이를 논리적으로 설명하자면

 

시작하는 부분을 먼저 정렬해서 한다면 아래의 사진처럼 1 , 7로 인해 2,4 | 4, 5 를 카운트 못하는 상황이 발생한다.

 

그렇기 때문에 끝나는 점을 기준으로 정렬을 한다.

 

솔직히 어느정도 이해는 했는데 먼가 제대로 확 이해가 되지는 않는 느낌이다 ㅠㅠ

 

일단 이러하다는 점을 인지하고 다음에 또 풀어보면서 잘 이해해보자 !!

 

*여기서 기본 count = 1임이 디폴트인 경우 첫 값을 받기전에 0으로 두고 시작하는 것도 좋은 방법이다.

 

import java.util.Arrays;
import java.util.Scanner;


class Data implements Comparable<Data>{
        int a;
        int b;
        public Data(int a, int b) {
                this.a = a;
                this.b = b;
        }

        @Override
        public int compareTo(Data o) {
                if (o.b == this.b) {
                        return this.a - o.a;
                } else{
                        return this.b - o.b;
                }


        }
}

class Main {
        private int solution(int n, Data[] data) {
             int count = 0, et = 0;
             for (Data o : data) {
                     if (o.a >= et) {
                             count++;
                             et = o.b;
                     }
             }
             return count;
        }



        public static void main(String[] args) {
                Main T = new Main();
                Scanner in = new Scanner(System.in);
                int n = in.nextInt();

                Data[] data = new Data[n];
                for(int i = 0; i < n; i++) {
                        data[i] = new Data(in.nextInt(), in.nextInt());
                }

                Arrays.sort(data);

                System.out.println(T.solution(n, data));
        }
}

 

그래서 내가 푼 것에 정렬 부분만 고쳤는데

 

시간 초과가 났다. 이는 틀리지 않았지만 시간이 초과난 경우일 수도 있다는 말이다.. 

 

사실상 DFS로 푼다는 것은 시간을 감수하고 사용하는 것이기에 시간복잡도 n을 유도하고 만든 문제에서는 당연히 시간초과가 난다!!

import java.util.Arrays;
import java.util.Scanner;


class Data implements Comparable<Data>{
        int a;
        int b;
        public Data(int a, int b) {
                this.a = a;
                this.b = b;
        }

        @Override
        public int compareTo(Data o) {
                if (o.b == this.b) {
                        return this.a - o.a;
                } else{
                        return this.b - o.b;  
                }


        }
}

class Main {
        static int answer = 0;

        private void DFS(int j, int n, Data[] data, int b, int count) {
                for (int i = j+1; i < n; i++) {
                        if ( b <= data[i].a) {

                                count++;
                                DFS(i, n, data, data[i].b, count);

                                return;
                        }

                }
                answer = Math.max(answer, count);
        }

        private int solution(int n, Data[] data) {
                int count = 1;
                for (int i = 0; i < n; i++) {

                        DFS(i, n, data, data[i].b, count);

                }
                return answer;
        }



        public static void main(String[] args) {
                Main T = new Main();
                Scanner in = new Scanner(System.in);
                int n = in.nextInt();

                Data[] data = new Data[n];
                for(int i = 0; i < n; i++) {
                        data[i] = new Data(in.nextInt(), in.nextInt());
                }

                Arrays.sort(data);

                System.out.println(T.solution(n, data));
        }
}