[ 자바스크립트(JavaScript) ] section07 - 9 - 결혼식

📍 section07 - 9 - 결혼식

피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 한다. 만약, 입력이 13 15라면 13시 정각에 피로연장에 존재하고 15시에는 존재하지 않는다. 피로연장에 동시에 존재하는 최대 인원을 출력하는 문제다.

 

이 문제도 greedy로 풀 수 있는 문제인데, 회의실 배정처럼 입력을 정렬을 하되, 정렬 기준을 결혼식에 등장하는 시간(s), 결혼식장에서 나가는 시간(e)으로 나눠서 오름차순으로 정렬을 해야 한다. 입력을 타임라인 형식으로 그려보면 다음과 같다.

 

 

여기서 주의할 점은 나간시간(e)은 포함하지 않으므로 오름차순으로 정렬할 때 들어오는시간(s)과 나가는시간(e)이 동일하면 e가 먼저 오게 설정한다.

 

1. 피로연에 등장하는 시간과 나가는 시간을 나눈다.
2. 시간을 오름차순으로 정렬하는데 시간이 같다면 나간 시간을 먼저 앞에 세운다. (나간 시간은 정각에 존재하지 않기 때문)
3. 반복문을 돌면서 s를 만나면 cnt++을 해주고, e를 만나면 cnt--를 해준다.
4. cnt의 최댓값을 갱신한다.

 

여담이지만, 문자를 기준으로 정렬하고 싶으면 charCodeAt() 함수를 사용해 비교 문자를 ASCII 코드로 바꾸어 준 다음, 값을 비교해주면 된다. 여기선 s의 ASCII코드는 115이고, e는 101이므로 e가 더 작다.

 

 

728x90

 

let n = 5;
let arr = [[14, 18], [12, 15], [15, 20], [20, 30], [5, 14]];

console.log(solution(n, arr));

function solution(n, arr) {
    let tL = [];

    for (let x of arr) {
        tL.push([x[0], "s"]);
        tL.push([x[1], "e"]);
    }

    tL.sort((a, b) => {
        if (a[0] === b[0]) return a[1].charCodeAt() - b[1].charCodeAt();
        else return a[0] - b[0];
    });

    let cnt = 0;
    let answer = 0;

    for (let x of tL) {
        if (x[1] === "s") cnt++;
        else cnt--;
        answer = Math.max(answer, cnt);
    }
    return answer;
}