Algorithm/구현

[프로그래머스/17676번/JavaScript] 추석 트래픽

문제

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

 

입력 형식

  • solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.

  • 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.

  • 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.

  • 예를 들어, 로그 문자열 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초 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)

  • 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.

  • lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

 

출력 형식

  • solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.

 

입출력 예

lines return
["2016-09-15 00:00:00.000 3s"] 1
["2016-09-15 23:59:59.999 0.001s"] 1
["2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"] 1
["2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"] 2
["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
["2016-09-15 00:00:00.000 2.3s", "2016-09-15 23:59:59.999 0.1s"] 1
이 아래부터는 제가 임의로 추가한 테스트 케이스입니다.
["2016-09-15 21:00:02.066 2.62s", "2016-09-15 21:00:00.748 2.31s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:57.421 0.351s", "2016-09-15 21:00:00.741 1.581s", "2016-09-15 21:00:00.966 0.381s", "2016-09-15 21:00:00.464 1.466s"] 7
["2016-09-15 23:59:59.999 0.001s", "2016-09-15 23:59:58.999 0.001s"] 1
["2016-09-15 00:00:00.000 3s", "2016-09-15 00:00:00.000 2.9s"] 2

서론

2016-09-15 01:00:04.001 2.0s과 같은 형식의 입력을 받는다는 것을 보고 '아.. 이건 Date 객체를 써야겠다.' 라고 생각했다. 사실 작년 하반기 C모 사의 코딩 테스트에서도 Date 객체를 쓰는 문제가 나왔었는데 그 때 그 문제를 못 풀었어서...ㅎ 이번에야말로 Date 객체를 제대로 써 보자는 마음으로 임하게 되었다...

 

Date 객체를 간만에 쓰다보니 이것저것 만지다가 안 건데 2016-09-15 01:00:04.001와 같은 형식으로 입력되면 밀리초 단위까지 입력된다는 사실을 알았다. 사실 객체를 출력해봐도 크롬 개발자 도구, MDN Web Docs 콘솔에서는 밀리초 단위가 안 보이고, 프로그래머스에서는 그냥 Date {}라고만 나와서 몰랐다..ㅎ 맨날 객체를 만든 뒤 +1, +500 등으로 수정했는데 이번에도 그렇게 하다가 '이럴 필요가 없구나' 하고 깨닫게 되었다. 밀리초 단위로 Date 객체를 다뤄본 건 어색해서 이제서야 안 사실이었다..ㅠ 부끄럽지만 지금에서라도 알았으니 이득!

 

풀이에 사용할 알고리즘 구상

일단 이 문제에서 가장 중요한, 짚고 넘어가야 하는 사실들이 있다. 이 문제에서는 처리시간이 시작 시간과 끝 시간을 포함한다는 것(문제에서도 굵은 글씨로 강조되어 있다.)과, T = 0인 경우는 없다는 것, 문제에서 주어지는 lines는 응답이 완료된 시간을 나타낸다는 것이다. 문제를 빠르게 읽다보면 놓칠 수 있는 포인트라고 생각이 든다. 실제로 문제를 다 풀고 프로그래머스 질문하기 게시글을 쭉 훑어보니 이 조건들을 놓친 분들이 꽤 많았다.

 

이제 본격적으로 문제에 접근해보도록 하자. 2016년 9월 15일 하루에 대한 모든 로그들이 입력되고, 우리는 이 로그들을 분석해서 초당 최대 처리량을 출력하면 된다. 그런데 시간의 최소 단위는 1밀리초이므로, 2016년 9월 15일 하루 전체를 1밀리초마다 그 때의 초당 최대 처리량을 구하려 하면 계산 횟수가 무려.. 몇인지는 모르겠지만 아무튼 엄청나게 많다. 무조건 시간 초과가 날 것이므로, 문제를 풀기 위해선 먼저 초당 최대 처리량을 구할 타이밍을 먼저 생각해야 한다. 그리고 그 타이밍은, 바로 매 로그마다 주어지는 응답 시작 시간과 응답 완료 시간이다. (나머지 시간에선 새로운 트래픽이 발생하거나 기존 트래픽이 사라지지 않으므로 초당 최대 처리량이 변하지 않기 때문에 초당 최대 처리량을 구할 필요가 없다.)

 

결론: 로그의 응답 시작 시간과 응답 완료 시간에만 초당 최대 처리량을 구해야 한다.

 

그래서 나는 로그의 응답 시작 시간과 완료 시간을 담을 배열 traffics를 만들었다. 그리고 그 배열 안에 모든 시작 시간과 완료 시간을 담을 때, 그 시간이 시작 시간인지 완료 시간인지 구분하기 위해서 시작 시간은 양수, 완료 시간은 -1을 곱해서 음수로 만들었다. 그 후 traffics에 담긴 시간들을 절댓값 기준으로 정렬하면, traffics는 로그의 응답 시작 시간과 응답 완료 시간이 시간 순서대로 정렬된 배열이 된다. 그리고 이 배열은, 위에서도 말했듯이 우리에게 초당 최대 처리량을 구할 타이밍을 제공해 준다.

 

여기까지 진행됐다면 문제를 본격적으로 풀 준비가 끝난 것이다. 이제 traffics의 모든 element마다 해당 element로부터 1초 동안의 처리량을 구하면 이것이 초당 처리량이 되고, 이렇게 모인 초당 처리량들 중 가장 큰 값이 문제에서 요구한 초당 최대 처리량이 되기 때문이다!

 

따라서 나는 시간을 입력받아 해당 시간으로부터 1초 동안 처리량을 계산해줄 함수를 하나 더 만들었다. 이 함수는 입력받은 시간, 트래픽에 대한 정보, 현재 처리량을 입력받아 앞으로 1초 동안의 처리량을 계산해 반환해준다. 계산 과정은 아래와 같다.

 

1. traffics 안에 1초 내로 응답 시작 시간이 있을 경우 처리량 +1
2. 응답 시작 시간을 입력받았는데 traffics의 다음 element가 다른 로그의 응답 시작 시간이면 건너뛴다.
3. 응답 완료 시간을 입력받았는데 traffics의 다음 element가 다른 로그의 응답 완료 시간이면 건너뛴다.

위 과정을 입력받은 시간으로부터 999초 뒤, 또는 traffics의 끝까지 진행한다.

이 문제에선 처리시간이 시작 시간과 끝 시간을 포함하기 때문에,
999초 뒤까지만 진행해야 입력받은 시간까지 포함해서 1000초가 된다.
1000초 뒤까지 보면 오답.

 

이 계산을 traffics의 모든 element에 대해서 진행하고, 계산 결과 중 최댓값이 문제의 최종 정답이 된다.

 

제출 코드

function count(time, traffics, curCount) {
    if (time < 0) curCount++;
    let idx = traffics.indexOf(time);
    while (idx++) {
        if (idx > traffics.length) break;
        if (Math.abs(traffics[idx]) - Math.abs(time) >= 1000) break;
        if (traffics[idx] * time > 0) continue;
        if (traffics[idx] > 0) curCount++;
    }
    return curCount;
}

function solution(lines) {
    let answer = 0;
    let traffics = [];
    let curCount = 0;
    lines.forEach(str => {
        let finishedTime = new Date(str.slice(0, 23));
        let gap = +str.slice(24).replace('s','') * 1000 - 1;
        traffics.push(finishedTime - 0 - gap); // start
        traffics.push((finishedTime - 0) * -1); // end
    });
    traffics.sort((a, b) => Math.abs(a) - Math.abs(b));
    traffics.forEach(time => {
        if (time > 0) curCount++;
        else curCount--;
        answer = Math.max(answer, count(time, traffics, curCount));
    });
    return answer;
}

 

회고

사실 이 글을 쓰면서 느낀 점인데, 내 코드는 굳이 traffics 안에 응답 시작 시간과 응답 완료 시간을 전부 구겨넣어서 읽는 사람이 읽기 불편한 코드가 됐다는 점을 느꼈다. 그냥 응답 시작 시간만을 담는 배열과 응답 완료 시간만을 담는 배열을 두 개 만들어서 각 배열마다 count()를 진행했으면 위 계산 과정에서 2번, 3번 과정의 건너뛰는 과정조차 필요 없었을 것이다. 더 짧고 이해하기 쉬운 코드를 만들 수 있었는데 이 점이 아쉬웠다. 그 밖에 Date 객체를 생성한 뒤 0을 더하거나 빼지 않으면 디버깅할 때 불편하다는 점도 알게 되었고, 이 문제를 풀면서 콘솔에서 Date 객체를 이것저것 만져보면서 Date 객체를 조금 더 이해한 시간이 된 것 같아서 좋았다. 앞으로는 코딩 테스트 문제에서 날짜 문제가 나오더라도 더 잘 풀 수 있지 않을까..

'Algorithm > 구현' 카테고리의 다른 글

[프로그래머스/42578번/JavaScript] 위장  (0) 2021.07.21
[백준/1194번/Java] 달이 차오른다, 가자.  (0) 2021.03.24
raejoonee