[Inflearn] 자바 알고리즘 문제풀이 #09-03 3. 결혼식(Greedy Algorithm)

문제

설명

현수는 다음 달에 결혼을 합니다.

현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.

피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다.

각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.

현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.

만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다.

 

입력 

첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다.

두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.

시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인으로 오는 시간과 가는 시간이 음이 아닌 정수로 표현됩니다.

 

출력 

첫째 줄에 피로연장에 동시에 존재하는 최대 인원을 출력하세요.

예시 입력 1 

5
14 18
12 15
15 20
20 30
5 14

예시 출력 1

2

 

 

 

내 풀이

import java.util.*;

class Time implements Comparable<Time> {
    public int s, e;
    public Time(int s, int e) {
        this.s = s;
        this.e = e;
    }

    @Override
    public int compareTo(Time o) {
        if(this.e == o.e) return this.s - o.s;
        else return this.e - o.e;
    }
}
public class Main9_3 {
    public int Solution(ArrayList<Time> arr, int n) {
        int cnt=0, answer=Integer.MIN_VALUE;
        Collections.sort(arr);

        int end_time=Integer.MAX_VALUE;
        for(Time ob : arr) {
            if(ob.s < end_time) {
                cnt++;
                answer = Math.max(cnt, answer);
            }
            else cnt--;
            end_time = ob.e-1;
        }
        return answer;
    }

    public static void main(String[] args) {
        Main9_3 T = new Main9_3();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Time> arr = new ArrayList<>();
        for(int i=0; i<n; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            arr.add(new Time(s, e));
        }
        System.out.println(T.Solution(arr, n));
    }
}

2-3시간 동안 머리를 쥐어 짜내면서 열심히 풀어 보려고 했으나,, 예제 테스트 케이스에 대해서만 통과했다.

최대한 코드를 간단히 구현해야 한다는 압박감과,, 반복적인 패턴은 보이지 않아 답답함,,,

반복적인 패턴 안에서 사람1의 가는 시간과, 사람2의 오는 시간이 같을 때 처리는 하지 못해 오답인 듯 하다.

 

 

 

선생님 풀이

package Main9;

import java.util.*;

class Time implements Comparable<Time> {
    public int time;
    public char state;
    public Time(int time, char state) {
        this.time = time;
        this.state = state;
    }

    @Override
    public int compareTo(Time o) {
        if(this.time == o.time) return this.state - o.state;
        else return this.time - o.time;
    }
}
public class Main9_3 {
    public int Solution(ArrayList<Time> arr) {
        int cnt=0, answer=Integer.MIN_VALUE;
        Collections.sort(arr);
        for(Time ob : arr) {
            if(ob.state == 's') cnt++;
            else cnt--;
            answer = Math.max(cnt, answer);
        }
        return answer;
    }

    public static void main(String[] args) {
        Main9_3 T = new Main9_3();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Time> arr = new ArrayList<>();
        for(int i=0; i<n; i++) {
            int sT=sc.nextInt();
            int eT=sc.nextInt();
            arr.add(new Time(sT, 's'));
            arr.add(new Time(eT, 'e'));
        }
        System.out.println(T.Solution(arr));
    }
}

그동안 class 객체 내 멤버변수를 int, int 타입으로 설정해서 state를 넣을 줄은 생각하지 못했다.

진짜 하나만 알고 둘은 모르는 깡깡ㅇㅣ... 언제 잘해지냐... 매번 몰라 매번....

다음 문제는 꼭 풀면 되지... 히잉.. 열심히 푼 문제라 못 풀어내서 조금 아쉽다.

 

 

 

결과