문제

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

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

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

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

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

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

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

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

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

코드

public class Reception {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        ArrayList<Time> list = new ArrayList<>();
        for(int i=0; i<(input1*2); i++){
            int start = in.nextInt();
            char state = 's';
            if(i%2 > 0) state = 'e';

            Time person = new Time(start, state);
            list.add(person);
        }
        int result = solution(list);
        System.out.println(result);
    }

    private static int solution(ArrayList<Time> list) {
        int answer = 0;
        int cnt = 0;
        Collections.sort(list);

        for(Time time : list){
            if(time.state == 's') cnt++;
            else cnt--;
            answer = Math.max(answer, cnt);
        }
        return answer;
    }

    static class Time implements Comparable<Time>{
        int time;
        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;
            return this.time-o.time;
        }
    }
}

설명

객체를 생성할때 처음에는 시작 시간과 끝 시간을 두어 큐에 담은 뒤 방문객이 있을때마다 큐에서 poll()한 뒤 size()를 재는 방식으로 접근했었다... 하지만 무슨 문제인지 테스트 케이스가 커질수록 답을 못 맞추더라 ㅜㅜ 아마 size를 재는 부분이나 poll하는 부분에 문제인거 같은데 못 맞춘 답들은 대부분 기대값보다 리턴값이 컸다 ㅜㅜ 그래서 강의의 문제를 어떻게 풀지에 대한 설명을 먼저 들었다.

강의에서는 먼저 나처럼 하나의 객체에 들어오는 시간과 나가는 시간을 모두 작성하는 것이 아닌 시작 시간과 나가는 시간을 각각의 객체로 따로 보았다. 이렇게 하니 solution에서 구분할때 해당 객체의 state값이 s인지 e인지에 따라 cnt의 증가와 감소만 신경쓰면 됐었다.

알고리즘 문제를 풀며 느끼는건 항상 답은 내가 생각하는 어렵고 복잡한 코드보다 훨씬 간단하고 쉽다...