문제 7 - 추석 트래픽

출처 : 카카오 신입 공채 1차 코딩 테스트 문제 해설 – tech.kakao.com

카카오 신입 공채 1차 코딩 테스트 문제 해설

 

---

7. 추석 트래픽(난이도: 상)

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

입출력 예제

예제 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초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.

---

[ 문제 설명 ]

 

# datetime() 함수를 어떻게 이용되고, 어떻게 작동되는지 알 필요가 있다

 

import datetime
 
myDatetime = datetime.datetime.strptime('2018-07-28 12:11:32', '%Y-%m-%d %H:%M:%S')
print(myDatetime)   # 2018-07-28 12:11:32

이런 식으로 작동되고 여기서 timestamp()를 작동시키면

 

import datetime
myDatetime = datetime.datetime.strptime('2018-07-28 12:11:32', '%Y-%m-%d %H:%M:%S').timestamp()
print(myDatetime)  # 2018-07-28 12:11:32
1532747492.0

요렇게 바뀐다. ( timestamp = 초 * 분 * 시 * 일 * 달 * 년이라고 생각하시면 된다 )

 

그리고 combined_logs라는 리스트 변수로 모든 요청과 시작을 튜플형태로 저장합니다. (시작은 1, 종료는 -1로 표시)

 

그다음 코드의 원리는 현재 값을 기준으로 그다음 값이 1초 이내로 들어오면 겹쳐진다고 판단하고, 시작 기호로 체크된 부분을 더해줌으로써 겹쳐지는 값을 찾는 과정입니다.

 

주석으로 자세하게 설명했으므로, 주석을 통하여 코드를 읽어보시면 이해가 될 것 입니다.

 

---

[ 코드 ]

 

import datetime


def solution(lines: str) -> int:
    # 로그의 시작, 종료 시각 저장
    combined_logs = []
    for log in lines:
        logs = log.split(' ')
        timestamp = datetime.datetime.strptime(logs[0] + ' ' + logs[1], "%Y-%m-%d %H:%M:%S.%f").timestamp()
        combined_logs.append((timestamp, -1))
        combined_logs.append((timestamp - float(logs[2][:-1]) + 0.001, 1))

    accumulated = 0
    max_requests = 1
    combined_logs.sort(key=lambda x: x[0])
    # print(combined_logs)
    # print(list(enumerate(combined_logs)))
    for i, elem1 in enumerate(combined_logs):
        current = accumulated
        # print(combined_logs[i:])
        # print(i, elem1)

        # 1초 미만 윈도우 범위 요청 수 계산
        for elem2 in combined_logs[i:]:
            print(elem2[1])
            if elem2[0] - elem1[0] > 0.999:  # 겹쳐지지 않을 경우 그뒤도 겹치지 않을 것이므로 break
                break
            if elem2[1] > 0:  # 겹쳐지고 시작기호이면 1이 더해진다.
                current += elem2[1]
        max_requests = max(max_requests, current)  # 최댓값 최신화
        # print(elem1, end=" ")
        accumulated += elem1[1]
        # print(accumulated, end=" ")
    
    return max_requests



logs = [
    "2016-09-15 20:59:57.421 0.351s",
    "2016-09-15 20:59:58.233 0.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",

]

sol = solution(logs)
print()
print(sol)

 

---

후기

 

어렵다고 나오는 문제도

 

이해를 하면 쉽게 느껴집니다.

 

막상 어려운 문제를 나중에 맞닥뜨리게 된다면

 

계속 생각하고 생각하면 풀 수 있지 않을까?

라는 희망을 가져 봅니다.