[프로그래머스] LV.3 추석 트래픽 (JS)

KG·2021년 4월 22일

알고리즘

목록 보기

30/61

문제

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 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	result
["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

풀이

2018 카카오 블라인드 테스트 1차에서 출제된 문제이다. 카카오 출제문제 답게 지문이 길다. 최근 경향은 어떨지 모르지만 이제까지 출제된 문제를 보면 문자열을 다루는 부분이나 시간 관련 처리 쪽으로 항상 1문제 정도는 꾸준히 출제되는 것 같다.

시간처리

시간 관련해서는 까다로운 점이 크게 2가지가 있다고 생각한다. 다음 2가지 사항을 항상 고려해주어야 하는 경우가 많다.

주어진 시간을 특정 단위로 변환 Ex. 시:분:초 -> milliseconds
시간 흐름의 경과 측정 방법

1번의 경우는 아마 대부분 milliseconds 단위로 변환하여 처리하는 상황이 많다. 특별한 이유가 있는 것은 아니고 계산하기 편하기 때문이다. 때문에 문제에서 요구하는 리턴값의 형태에 따라서 계산이 완료된 milliseconds의 값을 다시 시:분:초 의 형태로 바꾸어주는 등의 로직이 필요할 수 있다.

2번이 조금 까다로운데 문제에 조건에 따라 시간의 흐름을 계산하는 법이 모두 다르다. 가령 1 - 10 초까지 시간이 경과되었을 때 이를 10초의 시간이 흘렀다고 제시하는 문제가 있고, 9초의 시간이 지났다라고 제시하는 문제가 있다. 이를 잘 구분해주어 접근해야 한다.

따라서 해당 문제에서 시간과 관련된 부분을 먼저 정립하고 넘어가자. 문제에서 원하는 값은 시간과 관련된 값은 아닌 것을 확인할 수 있다. 우리는 초당 최대 처리량을 리턴하면 되기 때문에 milliseconds 단위로 주어진 시간을 처리하기만 하면 되기에 별도로 다시 특정 시간의 형태로 변환하는 로직을 처리할 필요는 없을 것이다.

또한 문제 제한 사항을 보면 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초" 동안 처리된 요청이라고 설명하고 있다. 즉 처음 시작시간을 포함하여 처리시간을 계산한다는 것을 유의해야 한다.

위의 사항을 염두해두고 먼저 주어진 시간을 milliseconds 단위로 변환해주는 함수를 하나 만들어주자.

const transTimeToMilliSeconds = (time) => {
  const hour = (time[0]*10 + time[1]*1) * 60 * 60;
  const minute = (time[3]*10 + time[4]*1) * 60;
  const seconds = time[6]*10 + time[7]*1;
  const millis = time[9]*100 + time[10]*10 + time[11]*1;
  const amount = (hour + minute + seconds) * 1000 + millis;
  
  return amount;
}

뭐가 이리 복잡하지? 라고 생각할 수 있지만 하나하나씩 보면 단순한 변환만 해주는 함수라는 것을 알 수 있다. 주어진 시간의 최소 단위가 milliseconds 이기 때문에 시간/분/초 각각의 단위를 모두 milliseconds 로 바꾸어주는 것이다. 각각의 단위는 60을 기준으로 변환되기 때문에 밑으로 내려갈 수록 60을 곱해주는 것이다. 유의할 점은 매개변수로 전달받는 time은 문자열이다. 때문에 이를 항상 정수형으로 먼저 바꿔주고 연산을 수행해야 한다. 위에서는 1의 자리 문자열 정수에 1을 곱해주어 정수형으로 변환후에 연산을 처리하고 있다. 따라서 해당 함수에 주어진 시간을 넘겨주면 그 시간을 milliseconds 단위로 변환한 값을 리턴받게 될 것이다.

초당 최대 처리량

주어진 시간은 모두 milliseconds 단위로 통일하는데 까지는 완료했다. 그렇다면 통일된 시간을 가지고 초당 최대 처리량을 어떻게 계산해 줄 지 생각해보자.

초당 최대 처리량을 계산하려면 특정 구간에 몇 개의 요청이 중복되어 겹치는지 확인할 수 있어야 한다. 이를 위한 가장 단순한 생각은 각각 요청의 모든 시작시간과 종료시간을 계산하고 이 구간 내에 몇 개의 요청이 존재하는지 체크하는 방법일 것이다. 그런데 시작시간과 종료시간을 계산하고 나서 다시 구간 내의 요청 여부를 검사하려면 모든 요청에 대해 중첩으로 반복문을 다시 돌려야 한다. 보다 빠른 시간내에 이를 체크할 수 있는 방법이 없을까?

다시 기본적인 사항에 집중해보자. 우리가 필요한 것은 초당 최대 처리량이다. 이는 특정 시작시간 ~ 종료시간 사이에 가장 많은 요청이 몰린 구간이 어디인지 파악하는 것이 필요하다. 그런데 해당 구간에 몇 개의 요청이 발생하는 지를 각 요청의 시작시간과 종료시간만 알고 있다면 계산해 줄 수 있을 것 같지 않은가?

각각의 요청은 모두 시작시간과 종료시간을 가지고 있을 것이다. 그렇다면 어떤 요청이 시작할때 카운트를 세주고 종료될때 카운트를 제거하면 해당 구간의 요청 개수를 알 수 있다. 이때 우리는 해당 구간에 중첩되는 요청 역시 카운트해주어야 한다. 즉 다음과 같은 아이디어를 도출할 수 있다.

각 요청의 시작시간과 종료시간을 모두 구한다.
각 요청은 시작시간에 들어갈 때 카운트 되고, 종료시간에 나올 때 다시 카운트를 제거한다.
각 요청을 시작시간을 기준으로 오름차순 정렬한다.
정렬된 요청을 시작시간에 카운트 올리고, 각 요청의 종료시간에 카운트 다운을 수행하며 max 값을 갱신한다.

즉 시작시간을 기준으로 현재 처리하고 있는 요청의 개수를 알 수 있기 때문에, 시작시간을 기준으로 오름차순 정렬을 하게 된다면 앞에서부터 차례대로 수행되고 있는 요청의 개수를 파악할 수 있다. 이때 각 요청은 종료시간에 다시 종료되어 카운트가 사라지기 때문에 요청의 총량은 오르락 내리락을 반복할 것이다. 즉 이 요청의 총량이 가장 max 일때가 초당 최대 처리량이 될 것이다. 따라서 특정 구간을 일일이 구할 필요 없이 단순히 한 번의 반복으로 초당 최대 처리량을 구해줄 수 있다.

이를 위해 먼저 시작시간과 종료시간을 구해주자. 이때 주의해야 할 사항이 있다. 위에서도 언급했듯이 시간의 흐름을 계산하는 것에 유의해야 한다. 만일 10초에서 20초의 시간의 흐름이 발생했다면 해당 문제에서는 이를 11초가 지난것으로 계산한다. 이를 고려하여 시작시간과 종료시간을 구해주는 코드는 다음과 같다.

const times = [];

for(const line of lines) {
  // 입력으로 주어지는 시간 관련 데이터를 공백 기준으로 분리
  // date는 사용하지 않는 데이터므로 변수명을 굳이 할당하지 않아도 상관없다
  // finish에는 요청이 종료된 시간, 즉 우리가 milliseconds 단위로 변환할 시간
  // duration은 요청이 지속된 milliseconds 단위 시간이 저장된다.
  const [date, finish, duration] = line.split(' ');
  // 위에서 만든 변환 함수를 이용해 finish 타임을
  // milliseconds 단위로 변환한다.
  const millis = transTimeToMilliSeconds(finish);
  // 시작시간은 변환된 finish - duration 이 된다.
  // 이때 duration은 소수점 단위로 주어지므로 이를 똑같이
  // milliseconds 단위로 만들어주기 위해 1000을 곱한다.
  // 또한 앞서 언급한 시간의 흐름을 고려하여 최종적으로 1을 더해준 값이 시작시간이 되어야 한다.
  const startTime = millis - duration.substr(0, duration.length-1)*1000 + 1;
  // 종료시간은 변환된 finish + 1초가 된다. (문제조건에 의해)
  // 여기서 1초는 milliseconds로 변환하면 1000이지만,
  // 앞서 언급한 시간의 흐름을 고려하여 999를 더해주어야 한다.
  const endTime = millis + 999;
  
  // 시작시간과 종료시간을 구분하여 times 배열에 넣어준다.
  // 구분하는 방법은 객체(Object) 또는 Map 등을 이용해도 되지만 
  // 여기서는 간단하게 배열을 넣어 구분해주었다.
  times.push(['START', startTime]);
  times.push(['END', endTime]);
}

위의 코드를 실행하고 나면 times 배열에는 각 요청의 시작시간과 종료시간이 들어있는 상태가 될 것이다. 우리는 여기서 시작시간을 기준으로 오름차순 정렬된 배열이 필요하다. 이때 한 가지를 더 주의해야 한다. 특정 요청의 시작시간이 다른 요청의 종료시간과 동일한 경우에는 특정 요청의 시작 시간이 먼저 배치되어야 한다. 왜냐하면 문제의 조건에 따라 특정 요청이 10초에 종료되는데 다른 요청이 10초에 시작되는 경우엔 10초라는 시간대에 2개의 요청이 존재하기 때문이다. 따라서 times 배열을 다음과 같이 정렬해주자.

// js 에서 sort 함수는 기본적으로 문자열을 오름차순 정렬한다.
// 따라서 -1을 리턴하도록 하면 문자열을 대상으로 내림차순 정렬이 된다.
// 우리는 A의 종료시간 == B의 시작시간일때 B의 시작시간이
// 먼저 배치되어야 하므로 'START'와 'END'의 순서를 고려해
// 내림차순 정렬을 수행해준다.
times.sort((a, b) => a[1] !== b[1] ? a[1] - b[1] : -1);

따라서 times 배열은 시작시간을 기준으로 정렬이 완료되었다. 이제 앞에서부터 차례로 START인 경우에는 카운트를 증가시키고, END인 경우에는 카운트를 감소시키며 max 값을 갱신하면 초당 최대 처리량을 구해줄 수 있다.

let answer = 0;
let count = 0;
for(const time of times) {
  if(time[0] === 'START') count++;
  else count--;
  
  answer = Math.max(answer, count);
}

return answer;

전체코드

주석을 제외한 전체 코드는 다음과 같다.

function solution (lines) {
  const times = [];
  for(const line of lines) {
    const [date, finish, duration] = line.split(' ');
    const millis = transTimeToMilliSeconds(finish);
    const startTime = millis - duration.substr(0, duration.length-1)*1000 + 1;
    const endTime = millis + 999;
    
    times.push(['START', startTime]);
    times.push(['END', endTime]);
  }
  times.sort((a, b) => a[1] !== b[1] ? a[1] - b[1] : -1);
  
  let answer = 0;
  let count = 0;
  
  for(const time of times) {
    if(time[0] === 'START') count++;
    else count--;
    
    answer = Math.max(answer, count);
  }
  
  return answer;
}
  
const transTimeToMilliSeconds = (time) => {
  const hour = (time[0]*10 + time[1]*1) * 60 * 60;
  const minute = (time[3]*10 + time[4]*1) * 60;
  const seconds = time[6]*10 + time[7]*1;
  const millis = time[9]*100 + time[10]*10 + time[11]*1;
  const amount = (hour + minute + seconds) * 1000 + millis;
  
  return amount;
}