[프로그래머스 lev3/JS] [1차] 추석 트래픽

문제 출처

프로그래머스 lev3 - [1차] 추석 트래픽

나의 풀이

// 시간을 전부 초단위로 변환하는 게 중요한데 소수점 계산에 겁먹지 말기주어진 문자열 중에서 응답 완료 시간(S)과 처리 시간(T)를 추출한다.
시간의 간격으로 계산해야 하므로 전부 초 단위로 변환한다.
hh는 3600을, mm은 60을 곱해주면 된다.
이때 소수점 연산을 하면 3자리보다 길어질 수 있는데, 정확한 연산을 위해서 올림처리하지 않았다.
(++ 처리시간이 0.001부터라고 했으므로 0.001을 더해줘야 한다.)

응답완료시간에서 처리 시간을 빼주면 시작시간이 도출되므로,
이를 기반으로 list, log 배열에 각각 삽입해준다.

log 배열을 사용한 이유는, 범위를 알기 위해서
list 배열을 사용한 이유는, 처음엔 객체를 생각했으나 예를 들어 시간을 key로 잡으면 중복 여지가 있으므로 결국 key 값으로 임의의 값을 할당해야 했다. 그럼 결국 배열을 사용하는 것과 다르지 않으므로.

임의의 지점에서 1초 간 가능한 데이터를 측정한다고 했는데, 모든 구간을 측정할 수 없을 것 같았다. 그리디 유형이라고 판단했다. 그래서 기준을 잡아야 했는데, 그게 log 배열이다. 각 배열에서 1초 더한 구간마다 겹치는 개수를 찾는다.

범위는 다음과 같이 나눌 수 있다.

• 왼쪽에 걸쳐 있는 경우
• 오른쪽에 걸쳐 있는 경우
• 왼쪽 오른쪽을 포함하는 경우

그리디 유형은 정렬을 자주 쓴다.

function solution(lines) {
  let answer = 0;
  const list = [];
  const log = [];

  lines.forEach((line) => {
    const [_, S, T] = line.split(" ");
    const [hh, mm, sssss] = S.split(":");

    const end = hh * 60 * 60 + mm * 60 + sssss * 1;
    const time = Number(T.slice(0, T.length - 1));
    const start = end - time + 0.001;

    list.push([start, end]);
    log.push(start, end);
  });
  // 범위를 알기 위해서 log 배열을 만들어서 전부 넣고 정렬을 하면 된다.
  log.sort();

  for (let i = 0; i < log.length; i++) {
    const testStart = log[i];
    const testEnd = log[i] + 1; // 각 시작점에서 1초

    let tempCount = 0;

    for (let j = 0; j < list.length; j++) {
      const currStart = list[j][0];
      const currEnd = list[j][1];

      // 시작지점이 범위 안에 들어오는 경우
      if (currStart >= testStart && currStart < testEnd) {
        tempCount++;
        continue;
      }
      // 끝지점이 범위 안에 들어오는 경우
      if (currEnd >= testStart && currEnd < testEnd) {
        tempCount++;
        continue;
      }
      // 범위보다 더 큰 경우
      if (currStart <= testStart && currEnd >= testEnd) {
        tempCount++;
        continue;
      }
    }
    answer = tempCount > answer ? tempCount : answer;
  }
  return answer;
}

알아내야 했던 정보.
1초당 처리량이 변경되는 시점은 요청이 시작하거나 끝나는 지점.

또 가능한 풀이 접근

• 그래프 : Array[1000 * 60 * 60 * 24]를 만들어서 접근하기(js로는 미친 짓에 가깝다)
• 슬라이딩 윈도우 : 오른쪽에서 들어오면 ++;, 왼쪽에서 나가면 --;

다른 풀이

현재 끝지점이 타겟의 시작지점보다 앞에 있으면 겹쳐 있으므로 ++

function solution(lines) {
  var answer = 0;

  for (var i = 0; i < lines.length - answer; i++) {
    // console.log(i);
    var Time = function (timeline) {
      var endDate = new Date(timeline.substring(0, timeline.lastIndexOf(" ")));
      var processingTime =
        timeline.substring(timeline.lastIndexOf(" ") + 1, timeline.length - 1) *
        1000;

      this.endTime = endDate.getTime();
      this.startTime = this.endTime - processingTime + 1;
    };

    var basisTime = new Time(lines[i]).endTime + 1000;

    var num = 1;

    for (var j = i + 1; j < lines.length; j++) {
      var target = new Time(lines[j]);

      if (target.startTime < basisTime) {
        num++;
      }
    }

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

다른 풀이 2

슬라이딩 윈도우.

function solution(lines) {
  /* timeString to timeNumber (ex. 00:01:00.002 => 60.002) */
  function toTimeNumber(timeStr) {
    const hours = Number(timeStr.substr(0, 2)) * 60 * 60 * 1000;
    const minutes = Number(timeStr.substr(3, 2)) * 60 * 1000;
    const seconds = Number(timeStr.substr(6, 2)) * 1000;
    const milliseconds = Number(timeStr.split(".")[1]);
    return hours + minutes + seconds + milliseconds;
  }

  /* 시작시간,종료시간 */
  const logs = lines
    .map((e) => e.slice(11).split(" "))
    .map((e) => [toTimeNumber(e[0]), Number(e[1].replace("s", ""))]);
  const times = logs
    .map((e) => [e[0] - e[1] * 1000 + 1, e[0]]) // times[i] includes [ 시작시간, 종료시간 ]
    .sort((a, b) => a[0] - b[0]); // 시작시간 기준 오름차순 정렬

  console.log(times);

  /* 시작시간 기준 순회 비교 */
  let max = 1;
  let window = [];
  times.forEach(([start, end]) => {
    window.push(end);
    window = window.filter((e) => e > start - 1000);
    if (window.length > max) max = window.length;
  });

  return max;
}