[JS] 코딩 테스트 문제 : 결혼식

문제 : 결혼식

문제 설명

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

피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다.
각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.
현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.

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

▣ 입력설명

첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.
시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인으로 오는 시간과 가
는 시간이 음이 아닌 정수로 표현됩니다.

▣ 출력설명

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

▣ 입력예제 1

5
14 18
12 15
15 20
20 30
5 14

▣ 출력예제 1

2

내코드

function solution(times) {
  // 동시 입장 최대 존재 인원 체크를 위한 변수
  let answer = Number.MIN_SAFE_INTEGER;
  // 현재 식장 존재 인원을 나타낼 변수
  let currentCount = 0;

  // 기존 2차원 배열에서 오는 시간과 가는 시간으로 각각 구분하여 오름차순 정렬한 뒤 저장
  let startTimeArr = times.map((t) => t[0]).sort((a, b) => a - b);
  let endTimeArr = times.map((t) => t[1]).sort((a, b) => a - b);
  // 오는 시간과 가는 시간을 특정 시간에 입출입 여부를 카운트할 때 사용할 각각의 index 변수
  startIdx = 0;
  endIdx = 0;

  // 가장 빠른 입장 시간부터 가장 늦은 퇴장 시간까지 1씩 증가하는 반복문
  // 입장되는 인원 및 퇴장하는 인원을 체크하기 체크하는 시간 t 와 비교해서 일치할 경우 입장의 경우 currentCount 1 증가 퇴장의 경우 1 감소
  // 입출입 인원들 체크가 완료된 후 현재 인원(currentCount)가 최대 존재 인원 수(answer) 를 넘어가는 경우에 반영
  for (let t = startTimeArr[0]; t <= endTimeArr.at(-1); t++) {
    console.log(t, endIdx);
    if (startTimeArr[startIdx] === t) {
      currentCount++;
      startIdx++;
    }
    if (endTimeArr[endIdx] === t) {
      currentCount--;
      endIdx++;
    }
    answer = Math.max(answer, currentCount);
  }
  return answer;
}

풀이

1. 기존 2차원 배열에서 오는 시간과 가는 시간으로 각각 구분하여 오름차순 정렬한 뒤 저장하고 각각의 배열에서 주소로 사용할 index 변수도 각각 생성
2. t 는 가장 빠른 입장 시간부터 가장 늦은 퇴장 시간까지 1씩 증가하는 반복문 안에서 체크하는 시간(t) 와 비교해서 일치할 경우 입장의 경우 현재 인원(currentCount) 1 증가 퇴장의 경우 1 감소
3. 입출입 인원들 체크가 완료된 후 현재 인원(currentCount)가 최대 존재 인원 수(answer) 를 넘어가는 경우 최대 존재 인원 수(answer) 를 업데이트
4. 최종적으로 최대 존재 인원 수(answer) 를 반환

보완할 수 있는 부분

// 기존코드
let answer = Number.MIN_SAFE_INTEGER;
let currentCount = 0;

let startTimeArr = times.map((t) => t[0]).sort((a, b) => a - b);
let endTimeArr = times.map((t) => t[1]).sort((a, b) => a - b);
startIdx = 0;
endIdx = 0;

for (let t = startTimeArr[0]; t <= endTimeArr.at(-1); t++) {
  console.log(t, endIdx);
  if (startTimeArr[startIdx] === t) {
    currentCount++;
    startIdx++;
  }
  if (endTimeArr[endIdx] === t) {
    currentCount--;
    endIdx++;
  }
  answer = Math.max(answer, currentCount);
}
return answer;

// 보완코드
let answer = Number.MIN_SAFE_INTEGER;
let T_line = [];

// 기존 2차원배열에서 1차원 배열로 입장 시간과 퇴장 시간을 한 배열에 특정 문자로 구분해서 저장('s' 는 입장시간 't' 는 퇴장시간을 의미)
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;
// 전체 배열만큼 순회하면서 's' 의 경우 입장한것을 의미하므로 cnt 1 증가 'e' 의 경우 퇴장한것을 의미 하므로 cnt 1 감소
for (let x of T_line) {
  if (x[1] === "s") cnt++;
  else cnt--;
  answer = Math.max(answer, cnt);
}
return answer;

기존에 각각의 1차원 배열로 구분해서 저장 후 다시 정렬해서 저장하던 방식에서 1차원 배열에 구분해서 저장 후 정렬

기존에 가장 빠른 입장 시간부터 가장 늦은 퇴장 시간까지 1씩 증가하는 반복문에서 정렬해둔 1차원 배열의 요소만큼만 순회하면서 처리하여 기존의 불필요한 반복 과정을 생략할 수 있다. 또한 불필요한 인덱스 변수가 필요하지 않다.

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard