[JS 알고리즘] 결혼식 (정렬과 그리디)

결혼식

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

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

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

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

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

 

입력설명

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

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

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

 

출력설명

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

 

입력예제

14 18 12 15 15 20 20 30 5 14

 

출력예제

2

 

// 내가 푼 것
function solution(times){
    let answer = Number.MIN_SAFE_INTEGER;

    // 1번 풀이
    let wedding = [...times]

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

    for(let i = 0; i < wedding.length; i++) {
        let tmp1 = wedding[i][0]
        let tmp2 = wedding[i][1]
        let cnt = 0
        for (let j = 0; j < wedding.length; j++) {
            if (wedding[j][0] >= tmp1 && wedding[j][0] < tmp2) {
                cnt++
            }
        }
        if (cnt > answer) {
            answer = cnt
        }
    }

    return answer;
}

let arr=[[14, 18], [12, 15], [15, 20], [20, 30], [5, 14]];
console.log(solution(arr));

이중 for문을 사용해 tmp1보다 앞 값이 크거나 같은 경우와 tmp2보다 앞 값이 작은 경우를 만족할 때 카운트를 추가했다. arr 값을 몇번 바꿔봤을 땐 풀렸지만, 모든 경우에서 풀릴것 같지는 않다는 생각이 들었다.

 

// 강의의 풀이
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();
        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));

강의에서는 T_line이라는 배열을 만들어 반복문으로 x[0]과 x[1]의 값을 start와 end로 분리했다. 그 다음 's'와 'e'를 캐릭터코드를 기준으로 정렬을 하고 x[1]이 's'일 때 카운트를 올리는 방식으로 문제를 풀었다. 동시에 수용이 가능한 경우가 최대가 될 때 Math.max로 answer에 넣어주기 때문에 최대값을 구하기가 쉬워진다.