[인프런 섹션7] 결혼식 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션7] 결혼식 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-27

1. 동시에 존재하는 최대 인원수 구하기

2. arr를 어떻게 정렬할 것인가?

• 시작시간 종료시간 상관없이, 배열에 등장한 모든 시간을 오름차순으로 정렬
• 단, 시작시간일 경우 cnt+1, 종료시간일 경우 cnt-1

let table = [];

for (let x of arr) {
    table.push([x[0], 1]);  // 시작시간일 경우 cnt+1
    table.push([x[1], -1]);  // 종료시간일 경우 cnt-1
}

table.sort((a, b) => a[0] - b[0]);

3. 정렬한 배열 table을 순회

let cnt = 0;
for (let x of table){
    cnt += x[1];
    max = Math.max(max, cnt);
};

4. 들어오는 사람과 +1 나가는 사람이 -1 동시에 존재할 경우

• cnt+0으로 처리해야 함
• 현 로직에서는 cnt+1을 먼저 처리하는 경우 max에 영향을 미침

5. 해결방법

• 방법 1. hash 사용하기 --> 문제점 : hash의 Map()은 삽입 순으로 순회하며, 정렬X
• 방법 2. 인접한 두 원소의 시간이 다른 경우에만 Math.max() 연산

let cnt = 0;
for (let i = 0; i < table.length; i++) {
    cnt += table[i][1];
    if (table[i][0] !== table[i + 1][0]) max = Math.max(max, cnt);
};

6. for 반복문 종료조건 수정

• table 마지막 원소를 순회할 때, table[i + 1][0] 오류 발생
• 들어온 인원은 반드시 나가야 하므로, table의 마지막 원소는 무조건 cnt-1
• 우리는 max 인원을 구하고 있으므로, table 마지막 원소는 순회하지 않아도 상관없다.

let cnt = 0;
for (let i = 0; i < table.length-1; i++) {
    cnt += table[i][1];
    if (table[i][0] !== table[i + 1][0]) max = Math.max(max, cnt);
};

---

4번의 또다른 해결방법

• table.sort() 할 때 시간이 같은 경우, -1 +1을 오름차순으로 정렬
• table 순회 로직 단순해짐

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

for (let x of table){
    cnt += x[1];
    max = Math.max(max, cnt);
};

✍️소스코드

2021-06-27

function solution(arr) {
    let max = 0, cnt = 0;

    let table = [];
    for (let x of arr) {
        table.push([x[0], 1]);   // 출입시간일 경우 cnt+1
        table.push([x[1], -1]);   // 퇴장시간일 경우 cnt-1
    }
    table.sort((a, b) => a[0] - b[0]);

    for (let i = 0; i < table.length-1; i++) {
        cnt += table[i][1];
        if (table[i][0] !== table[i + 1][0]) max = Math.max(max, cnt);
    };
    return max;
}

2021-06-27

function solution(arr) {
    let max = 0, cnt = 0;
    let table = [];

    for (let x of arr) {
        table.push([x[0], 1]);   // 출입시간일 경우 cnt+1
        table.push([x[1], -1]);   // 퇴장시간일 경우 cnt-1
    }

    table.sort((a, b) => a[0]===b[0] ? a[1]-b[1] : a[0]-b[0]);

    for (let x of table) {
        cnt += x[1];
        max = Math.max(max, cnt);
    };

    return max;
}