[알고리즘] 9-3 결혼식 - Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-03

풀이

친구들 5명의 (도착시간, 떠나는시간)이 다음과 같을 때,
(14, 18), (12 ,15), (15, 20), (20, 30), (5, 14)

시간의 흐름을 그림으로 나타내면 다음과 같다.

class Time implements Comparable<Time>{
    int time;
    char status;//S: 도착시간, E: 떠나는 시간

    public Time(int time, char status) {
        this.time = time;
        this.status = status;
    }

    @Override
    public int compareTo(Time o) {
        if (this.time == o.time)
            return this.status - o.status;
        else
            return this.time - o.time;
    }
}

//결혼식
public class Main9_3 {

    public static int solution(List<Time> list) {
        int answer = 0; //최대 인원수
        int count = 0; //현재 피로연에 있는 인원수

        Collections.sort(list);

        for (Time t : list) {
            //정렬된 리스트를 순차적으로 돌며 status가 S이면 count 변수를 1증가 시키고, E이면 1감소시킨다.
            if (t.status == 'S') {
                count++;
                answer = Math.max(answer, count);
            } else
                count--;
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        List<Time> list = new ArrayList<>();

        StringTokenizer st = null;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            list.add(new Time(start, 'S')); //도착 시간
            list.add(new Time(end, 'E')); //떠나는 시간

        }

        System.out.println(solution(list));

        br.close();
    }
}

문제 조건에 떠나는 시간은 사람이 이미 떠나고 존재하지 않는 시간이라고 제시되어있기 때문에, 같은 시간일 경우 떠나는 사람의 시간이 정렬상 앞에 있도록 정렬하여 count를 감소시키는 작업이 먼저 실행되도록 해야 한다.

도착 시간이 앞에 있게 되면 떠나는 사람이 이미 없는 시점임에도 불구하고, count를 감소시키지 못한 채 도착한 사람의 count를 증가시켜 버리기 때문에 최대 인원수가 잘못 갱신되기 때문이다.