2022/03/21) 9. 결혼식 [정렬과 그리디, 결정알고리즘]

1. 문제

<결혼식>
: 결혼식 피로연을 3일간 쉬지 않고 하려고 하는데, 참석하는 친구들(N명)의 참석하는 시간정보를 미리 요구했다. 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 한다. 피로연장에 동시에 존재하는 최대 인원을 출력하라.

2. 해결 방법

1. 타임라인으로 그림을 그려본 후, 도착하는 시간을 's'로 떠나는 시간을 'e'로 해서 새 배열(T_line)을 만들어 보자.
2. 그 후 새배열을 정렬하는데, 같은 시간대일 경우엔 e->s 순으로 정렬한다.(유니코드 이용)
   sort함수는 반환값이 0보다 작으면 a를 우선하여 정렬한다는 거 명심!
3. 's'를 만나면 cnt++, 'e'를 만나면 cnt--를 한다. 그 후 Math.max로 answer과 cnt의 값을 비교해서 큰 값을 answer에 넣는다.

3. 정답

        <script>
            function solution(times){
                let answer = Number.MIN_SAFE_INTEGER;
                let T_line = []; //타임라인
                for(let x of times){
                    T_line.push([x[0], 's']);
                    T_line.push([x[1], 'e']);
                }
                T_line.sort((a,b) => {
                    if(a[0] === b[0]) return a[1].charCodeAt()-b[1].charCodeAt(); //시간이 같을 땐 e가 먼저 오도록 해야함
                    else return a[0]-b[0];
                })
                let cnt = 0;
                for(let x of T_line){
                    if(x[1] == 's') cnt++
                    else cnt--;
                    answer = Math.max(answer, cnt);
                }
                return answer;
            }
            let arr=[[14, 18], [12, 15], [15, 20], [20, 30], [5, 14]];
            console.log(solution(arr));
        </script>

4. 후기

그리디가 무조건 끝의 시간으로 정렬하는 게 아니구나. 그냥 문제에 따라 오름차순 혹은 내림차순으로 정렬하는 게 그리디정렬인 거 같다. 조금 헷갈리는데 그림그려서 해보도록 하자!