[카카오 기출문제] '추석 트래픽' 문제 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

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

 

입출력 예

예제 번호	INPUT	RETURN
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
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

 

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번 예제 설명

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

 

 

알고리즘 분석

 

• 나의 풀이

def data_process(data):  # 문자열을 사용하기 좋은 데이터 형태로 가공 
    date, time, runtime = data.split(' ')  # 날짜(안씀), 시간, 실행시간으로 분리
    hour, minute, second = time.split(':') # 시, 분, 초로 분리
    end_time = int(hour) * 3600 + int(minute) * 60 + float(second) # 시간을 초단위로 변환 
    # 소수점을 없애고 정수로 쓰기 위해서 1000을 곱해줌 
    end_time, runtime = int(end_time * 1000), float(runtime[:-1]) * 1000 
    return [end_time - int(runtime) + 1, end_time] # [시작시간, 종료시간]을 반환

def solution(traffic):
    answer, stack = 0, []  # 정답, 스택 
    traffic = list(map(data_process, traffic))  # data_process 함수로 데이터를 변환 
    traffic.sort(key=lambda x: x[0])  # 시작시간 순으로 정렬 
    for traf in traffic:
        del_stack = []
        start_time, end_time = traf[0], traf[1]  # 시작시간, 종료시간
        for s in stack:  # 스택이 있다면 반복
            if start_time > s:  # 시작시간이 스택(종료시간)보다 크다면
                stack.remove(s) # 스택에서 지워줍니다.
        stack.append(end_time+999) # 스택에 "종료시간 + 1초(999)"를 추가 
        if len(stack) > answer: # stack의 크기가 answer보다 크다면 
            answer = len(stack)
    print(answer)
    return answer

 

stack을 리스트가 아닌 집합 자료형으로 사용했다가 삽질을 엄청나게 했다. 

처음에는 정렬의 문제인가 싶어서 정렬을 해보고 

999가 아니라 1000이 들어가야되는 건지 이것저것 실험해보고

다른 블로그까지 찾아봤는데 자료형이 문제였다. 

중복되는 값이 2개가 존재할 경우 집합 자료형은 한개의 요소로 판단한다는 것을 깜빡했다. 

 

결국 자료형을 바꿨는데 아직 틀린 경우가 있어서 고생 끝에 찾았는데

이미 한번 시도해본 정렬이 문제였다.... 

정렬한거 그대로 놔뒀으면 성공이었는데 괜히 안된다고 지웠다가 생고생했다 ㅋ

 

항상 중복되는 값을 고려해야된다는 것을 잊지말자!