[JS] 추석 트래픽 - 드디어 '나' 레벨 3 입성!

에... 드디어 레벨 3에 도착했네요

앞으로는 레벨 3 하나 레벨 2 하나 이런 병행으로 가겠습니다.

 

오늘은 기념비적인 레벨3의 첫 문제인 2018 KAKAO BLIND RECRUITMENT 1차에 나왔던 추석 트래픽을 해봤습니다.

date에 관한 문제인데요. Javascript 에서는 Date 객체가 지원되기 때문에 연산이나 비교에 대한 간단한 팁을 정리해두면 그래도 편하게 풀 수 있습니다.

 

같이 한 번 보죠!

---

문제 요약

추석 트래픽

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

 

입력 형식

• 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 "2016년 9월 15일 오전 3시 10분 33.010초"부터 "2016년 9월 15일 오전 3시 10분 33.020초"까지 "0.011초" 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)

 

테스트케이스

예제1

• 입력: [
  "2016-09-15 01:00:04.001 2.0s",
  "2016-09-15 01:00:07.000 2s"
  ]
• 출력: 1

예제2

• 입력: [
  "2016-09-15 01:00:04.002 2.0s",
  "2016-09-15 01:00:07.000 2s"
  ]
• 출력: 2
• 설명: 처리시간은 시작시간과 끝시간을 포함하므로
  첫 번째 로그는 01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며,
  두 번째 로그는 01:00:05.001 ~ 01:00:07.000에서 2초 동안 처리된다.
  따라서, 첫 번째 로그가 끝나는 시점과 두 번째 로그가 시작하는 시점의 구간인 01:00:04.002 ~ 01:00:05.001 1초 동안 최대 2개가 된다.

예제3

• 입력: [
  "2016-09-15 20:59:57.421 0.351s",
  "2016-09-15 20:59:58.233 1.181s",
  "2016-09-15 20:59:58.299 0.8s",
  "2016-09-15 20:59:58.688 1.041s",
  "2016-09-15 20:59:59.591 1.412s",
  "2016-09-15 21:00:00.464 1.466s",
  "2016-09-15 21:00:00.741 1.581s",
  "2016-09-15 21:00:00.748 2.31s",
  "2016-09-15 21:00:00.966 0.381s",
  "2016-09-15 21:00:02.066 2.62s"
  ]
• 출력: 7

설명: 아래 타임라인 그림에서 빨간색으로 표시된 1초 각 구간의 처리량을 구해보면 (1)은 4개, (2)는 7개, (3)는 2개임을 알 수 있다. 따라서 초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.

접근 방법

제가 생각하는 이 문제의 핵심은 1초의 시간이 0초 ~ 1초가 아니라는 겁니다.

0.000초 ~ 0.999초로 계산하셔야 해요. 그러니까 date 연산할때 seconds를 1늘린 다음에 milliseconds를 1 줄여줘야하는 번거로움이 있습니다.

 

하면서도 이게 맞나...? 싶었지만 일단 돌아는 가네요. 변수를 이상하게 써서 가독성이 안 좋습니다. 순서를 유의 깊게 봐주시면 조금 이해가 편하실 거라고 생각됩니다.

 

solution.js flow

1. timeTable의 정의
   1. "년도-월-일 시:분:초.ms 초.ms" 제공된 row data를 공백에 따라 split을 해줍니다.
   2. "시:분:초.ms"의 가운데 .을 기준으로 분리해줍니다. (따로 ms를 추출합니다.)
   3. "초.ms"의 가운데 .을 기준으로 분리해줍니다. (따로 ms를 추출합니다.)
   4. 적절히 계산하여 api의 [처리시작시간, 종료시간]으로 return 해줍니다.
2. timeTable의 순회
   1. start(api 처리 시작 시간) ~ start + 1 사이에서 처리중인 task를 세어줍니다.
   2. end(api 처리 종료 시간) ~ end + 1 사이에서 처리중인 task를 세어줍니다.
3. 처리중인 task가 가장 많은 값을 return 해줍니다.

예시로 나온 time chart에서 확인할 수 있지만, 가장 많은 처리량이 있는 구간은 딱 api가 시작될때나 끝날때 일 수 밖에 없습니다. 순간 처리량이 가장 많은 시기이거든요.

 

자 서론이 길었네요. 정답 코드를 보시죠!

 

정답 코드

function count(timeTable, start, end) {
    const [startVal, endVal] = [start.getTime(), end.getTime()];
    let result = 0;
    for (const dealTime of timeTable) {
        const dealStart = dealTime[0].getTime();
        const dealEnd = dealTime[1].getTime();
        if (dealEnd < startVal || endVal < dealStart) continue;
        result++;
    }
    return result;
}
function solution(lines) {
    const timeTable = lines.map((row) => {
        const [date, time, period] = row.split(" ");
        const [s, ms] = time.split(".");
        let [deals, dealms] = period.slice(0, period.length - 1).split(".");
        const end = new Date(`${date} ${s}`);
        end.setMilliseconds(ms);
        const start = new Date(end);
        start.setSeconds(start.getSeconds() - Number(deals));
        if (dealms) {
            if (dealms.length < 3) dealms = dealms + '0'.repeat(3 - dealms.length);
            start.setMilliseconds(start.getMilliseconds() - Number(dealms) + 1);
        } else {
            start.setMilliseconds(1);
        }
        return [start, end];
    });
    
    let index = 0;
    let result = [];
    while (index < timeTable.length) {
        const [start, end] = timeTable[index];
        const [startend, endend] = [new Date(start), new Date(end)];
        startend.setSeconds(startend.getSeconds() + 1);
        startend.setMilliseconds(startend.getMilliseconds() - 1);
        endend.setSeconds(endend.getSeconds() + 1);
        endend.setMilliseconds(endend.getMilliseconds() - 1);
        result.push(count(timeTable, start, startend));
        result.push(count(timeTable, end, endend));
        index++;
    }
    
    return Math.max(...result);
}

 

팁 1. Date 객체의 활용

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Date

Date - JavaScript | MDN

const end = new Date('2022-07-30');

const end2 = new Date('2022-07-30 15:00:00');

const end3 = new Date('July 30, 2022 15:00:00');

 

다양한 방식으로 활용할 수 있습니다. 꼭 string 객체가 아니어도 됩니다. timestamp 형식의 number도 들어가도 됩니다.

문제는 ms를 따로 설정해줘야한다는 점이겠네요.

그래서 timeTable 정의 테이블이 약간 지저분해요. 따로 ms 부분을 split 한 뒤에 나중에 설정해줬습니다.

 

ms를 설정하는 방법은 이런 식으로 하시면 되겠습니다.

const start = new Date(null);
start.setSeconds(start.getSeconds() - 100);

 

지금 시간기준으로 100ms 즉 0.1초 이전을 정의하고 싶다면 이런 식으로 정의하시면 됩니다.

이 문제는 1초를 0.000초부터 0.999초로 정의하고 있기 때문에 1초 계산을 해주실때 꼭 ms를 1더해주는 거 잊으시면 안되겠습니다.

 

팁 2. Date 객체의 비교

const a = new Date();
const b = new Date();

//가능
if (a > b) return true;
if (a < b) return true;

//불가능
//if (a === b) return false;
//if (a !== b) return false;

const [aTime, bTime] = [a.getTime(), b.getTime()];

if (a <= b) return true;
if (a >= b) return true;

 

일반적인 Date 객체는 대소 관계 비교는 가능하지만 값이 일치하는지 여부는 확인이 불가능합니다.

문제 제한사항에서 처리 시작 시간과 종료시간이 포함되어야 한다고 써있기 때문에 저희는 getTime() 함수로 Date 객체를 timestamp로 변환하여 비교해줍시다!

 

레벨 3 문제는 역시 다르네요. 단순한 자료구조를 넘어서서 다양한 기능이나 더 심화된 내용을 묻는 느낌이 듭니다. 더 많이 공부할 수 있을 것 같습니다.

 

그럼 이만!