[프로그래머스/Javascript] 추석 트래픽

1️⃣서론

프로그래머스 level3 문제 추석 트래픽입니다. Javascript를 이용하여 해결하였습니다.

2️⃣문제 설명

추석 트래픽1 추석 트래픽2 추석 트래픽3

3️⃣풀이

이 문제는 카카오 신입 공채 1차중 가장 정답률이 낮았던 문제였습니다. 로그데이터를 보고 가장 트래픽이 많았던 양을 구하는 문제입니다. 문제에 대한 이해 자체는 쉬웠으나 항상 카카오의 난관인 구현력이 상당히 어려웠고 더하여 시간복잡도도 고려해야하는 문제가 있었습니다.
저도 풀다가 어려워서 다른 사람의 코드를 참조해서 풀었습니다. 풀이는 다음과 같습니다.

먼저 로그데이터를 [시작초, 끝초, 구간]으로 나눈다.
추가적으로 모든 로그데이터의 시작초와 끝초를 넣는다.
모든 로그데이터의 시작초와 끝초가 들어있는 배열을 돌면서 해당 구간에 데이터가 몇개가 존재하는지 셉니다.
그 후 가장 많은 카운터를 구하고 리턴합니다.

2번을 추가로 배열을 넣는 이유는 시간복잡도 때문인데요. 카카오 해설을 보면 알 수 있듯이 시작초와 끝초사이의 1초씩 건너뛰며 검사하는 것은 많은 시간이 걸리기 때문에 더 효율적인 방법인 시작초와 끝초만을 검사하는 방법을 쓰는 것입니다. 이 방법을 쓸 수 있는 이유는 바로 초당 처리량이 변하는 구간은 바로 데이터가 시작할때와 끝날때 뿐이기 때문입니다.

4️⃣ 내가 푼 소스코드

const solution = (lines) => {
  let answer = 0;
  const arr = [];
  const logPointArr = [];

  //1. 로그데이터를 나누고 시작초와 끝초를 새로운 배열에 담는다.
  for (let i = 0; i < lines.length; i++) {
    const line = lines[i].split(" ");
    const edSec =
      Number(line[1].substring(0, 2)) * 3600 +
      Number(line[1].substring(3, 5)) * 60 +
      Number(line[1].substring(6, 12));
    const duration = Number(line[2].substring(0, line[2].length - 1));
    const stSec = edSec - duration + 0.001;
    arr.push([stSec, edSec]);
    logPointArr.push(stSec, edSec);
  }

  //시작초와 끝초를 정렬한다 순서대로 순회하기 위해서..
  logPointArr.sort();
  console.log(logPointArr);

  for (let i = 0; i < logPointArr.length; i++) {
    const beginRange = logPointArr[i];
    const endRange = logPointArr[i] + 1;
    let count = 0;
    for (let j = 0; j < arr.length; j++) {
      const stPoint = arr[j][0];
      const edPoint = arr[j][1];

      //위 경우는 세가지로 나눌 수 있다 : 1. 시작점이 범위에 포함될때, 2.끝점이 범위에 포함될때,
      //3.시작점과 끝점사이가 범위에 포함될때
      if (
        (stPoint >= beginRange && stPoint < endRange) ||
        (edPoint >= beginRange && edPoint < endRange) ||
        (stPoint <= beginRange && edPoint >= endRange)
      ) {
        count++;
      }
    }

    if (count > answer) {
      answer = count;
    }
  }
  return answer;
};

5️⃣ 결론

지금까지 풀었던 카카오 문제중에 가장 어려운 문제가 아니었나 싶습니다. 일단 시간복잡도를 고려해야 한다는 문제가 이 문제가 처음이었고, 시작초와 끝초를 기준으로 잡고 센다는 점을 생각하는 것이 상당히 어려웠던 문제인것 같습니다. 아직 많이 부족해서 좀더 열심히 해야겠습니다.

6️⃣ 마치며..

질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️