결혼식

결혼식

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

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

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

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

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

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

입력 설명

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

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

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

출력 설명

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

입력

5
14 18
12 15
15 20
20 30
5 14

출력

2

구현 코드

public class 결혼식 {
    public static void main(String[] args) {
        ArrayList<Time> list = new ArrayList<>();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int i=0;i<n;i++){
            list.add(new Time(in.nextInt(),'s'));
            list.add(new Time(in.nextInt(),'e'));
        }

        Collections.sort(list, new Comparator<Time>() {
            @Override
            public int compare(Time o1, Time o2) {
                if(o1.time ==o2.time){
                    return o1.status - o2.status;
                }
                return o1.time - o2.time;
            }
        });

        int cnt = 0;
        int answer = Integer.MIN_VALUE;
        for(Time t : list) {
            if(t.status=='s'){
                cnt++;
            }
            else if(t.status == 'e'){
                cnt--;
            }
            if(cnt>answer){
                answer = cnt;
            }
        }
        System.out.println(answer);

    }

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

처음에 생각했던 방식은
Time class에 arriveTime과 leaveTime을 선언.
ArrayList에 add.
for문을 0부터 72까지 돌려서 list에 있는 객체들을 하나씩 검사하면서 진행하는 방식으로 생각.

생각하다보니 for문 안에서 어떤식으로 하나씩 빼서 비교하고 카운트할지..? 감이 안왔음. 강의 참고 후 어떤식으로 해야하는지 이해했음.

• 알고리즘
  

  Time class에 time과 status를 선언 (status: start time인지, end time인지)
  ArrayList에 add.
  list를 시간 오름차순으로 정렬. 만약 시간이 같을 경우 status end가 먼저 오게 정렬.
  list 돌면서 status가 s인 경우는 cnt++, e인 경우는 cnt--
  cnt>answer인 경우에만 answer 값 업데이트.

• list 정렬 시 시간이 같으면 end가 먼저 오게 정렬하는 이유
  그림과 같이 주어진 상황에서 만약 list가 시간 오름차순, 시간 같은 경우에는 s가 먼저오게 정렬된다면 다음과 같을 것임.
  5 s
  12 s
  14 s
  14 e
  15 s
  15 e
  18 e
  20 s
  20 e
  30 e
  이런 경우에 14 s까지 cnt가 ++되어 answer가 3이 되는데 end시간은 실제로 존재하지 않는 시간이라고 했으므로 실제로 겹치는 건 2. 따라서 이를 막기 위해 e가 먼저오게 정렬.