문제

풀이

package Inflearn.greedy.wedding;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Time> timeList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int startTime = sc.nextInt();
            int endTime = sc.nextInt();

            timeList.add(new Time(startTime, 's'));
            timeList.add(new Time(endTime, 'e'));
        }
        System.out.println(new Main().solution(timeList));
    }

    public int solution(List<Time> timeList) {
        int maxPeople = 0;
        int peopleCount = 0;
        Collections.sort(timeList);
        for (Time time : timeList) {
            if (time.getState() == 's') {
                peopleCount++;
                maxPeople = Math.max(peopleCount, maxPeople);
            }
            if (time.getState() == 'e') {
                peopleCount--;
            }
        }
        return maxPeople;
    }

}

class Time implements Comparable<Time> {

    private int time;
    private char state;

    public char getState() {
        return state;
    }

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

    public int compareTo(Time time) {

        if (this.time == time.time) {
            return this.state - time.state;
        }
        return this.time - time.time;
    }
}

처음엔 배열로 시간에 맞는 index에 값을 넣어줘서 그 중 가장 큰 값을 구하였다.
아마 입력값이 많아지면 for문이 많이 사용되어 프로그램 실행시간이 길어졌을 것 이다.

이전 그리디 문제와 비슷하게 정렬을 이용하는 문제였다. 조금 다른점은 시작시간과 끝난시간을 구분을 위한
char state였다. 시작 시간에는 's'를 같이 끝난 시간에는 'e'로 상태를 표시하였고, 상태를 확인하여 peoplw count의 값을 더해주고 빼주었다.

이 문제에 핵심은 같은 시간에 시작 시간과 끝난 시간이 겹치는 경우였는데 's'와 'e'도 정렬을 통해서
'e'가 무조건 먼저 정렬되게 중요하였다. 그리디 알고리즘은 시간을 더 투자해서 감을 잡는게 중요할 것 같다.