[프로그래머스 level3 추석 트래픽] 날짜를 수식으로 생각하기 !

3단계는 첫 문제부터 역시 쉽지 않은 것 같다...😂

문제의 조건을 생각하는 데에 있어 굉장히 많은 시간이 걸린 것 같다..

 

해결해야 하는 문제는 다음과 같았다.

programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [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를 기준으로 오름차순 정렬되어 있다.

 

출력 형식

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

  

 

 

 

이 문제에서 주어진 문제를 보고 컴퓨터 네트워크 시험문제에서 본 그림과 되게 닮았다고 생각했다.

1년 반 ? 만에 궁금해서 다시 시험지를 보았는데, 이는 CSMA/CA내용에서 본 그림과 비슷하게 생겼다.

CSMA/CA(Carrier Sense Multiple Access/ Collision Avoidance)는 무선 LAN에서 사용되는 mac 알고리즘으로, 데이터 전송 시 충돌을 예방하기 위해 데이터 전송에 대한 신호를 주고받으며 충돌되지 않도록 데이터 송수신을 하도록 한다.

이는 데이터 송수신과는 약간 다른 개념이지만, 시간을 나누어서 데이터 전송 시점을 알아보는 그림으로 인해 옛 기억이 난 것 같다.😮

사족은 접어두고, 문제를 풀자✏️

 

 

---

 

1. 데이터 배열로 들어오는 시간을 숫자 형식으로 통일하기

time_list는 시작 시간과 끝나는 시간을 담기 위한 배열이다. 이 배열에는 파라미터로 받은 lines 배열을 가공하여 넣을 것이다.

tmp에는 공백을 기준으로 문자열을  split하여 저장하였다.

입력이 아래와 같다면,

입력: [
"2016-09-15 01:00:04.002 2.0s"
]

tmp에는 ["2016-09-15","01:00:04.002","2.0s"] 가 저장된다.

 

long_time은 걸린 시간을 저장하기 위해 tmp[2]인 "2.0s"에서 s를 제외한 문자열을 float 형식으로 바꾸어주었다. 구간은 현재 구간을 포함하고 0.001 단위로 쪼개지므로 -0.001을 하였다.

 

time은 tmp[1]에 저장된 "01:00:04.002"을 ':' 기준으로 쪼개어 저장하였다.

우선 시작 시간을 구하기 위해서 second, minute, hour을 생성하였다.

second는 초에 해당하는 것이므로 time[2]배열에 해당하는 값에서 걸린 시간인 long_time을 빼주었다. 이 문제에서는 소숫점 3자리까지를 가지고 계산하기 때문에 round()를 통해 소숫점 3자리까지만 나타냈다.

minute과 hour는 각각 time[1], time[0]의 자리에 해당하므로 이에 대한 수를 집어 넣어주었다.

 

start_time은 second, minute, hour를 더해주었다. 여기서 주의할 점은 아래와 같다.

60초 = 1분
60*60초 =60분 = 1시간 

이러한 시간의 초개념을 이용하여 start_time, end_time을 구하였고, 이는 time_list에 저장하였다.

 

※이 문제는 2016-09-15에 대한 트래픽양만 확인한다.※

하지만 2016-09-15 00 :00 일 때 전송 시간이 2016-09-15 전날 인 경우, 2016-09-14 도 나올 수 있다.

아래 코드와 같이 작성하면, 2016-09-14는 음수값을 가지게 되며, 2016-09-15보다 앞의 수를 가지게 되므로 자연스럽게 처리가 가능해진다.

 

# [start_time, end_time]
    time_list = []
    for i in lines :
        tmp = i.split()
        long_time = float(tmp[2][:-1])-0.001
        time = tmp[1].split(':')
        second = round(float(time[2])-long_time,3)
        minute = int(time[1])
        hour = int(time[0])
        start_time = 60*60*hour + 60*minute + second
        end_time = 60*60*hour+ 60*minute+ round(float(time[2]),3)
        time_list.append([start_time,end_time])

 

 

 

2. 데이터 전송시작 시점과 데이터 전송 종료 시점에서의 최대 처리량 구하기

데이터를 전송하기 시작한 경우와 데이터 전송을 완료한 후에만 총 처리량이 변화한다.

따라서, 데이터 전송을 시작한 시각으로부터 1초간의 처리량을 확인하고, 데이터 전송을 완료한 시각으로부터 1초간의 처리량을 확인하도록 하였다.

그림으로 표현한 데이터 처리량 변화

첫 번째 막대를 확인하는 경우, 첫 시작으로부터 1초 간 2개의 데이터 전송이 처리되었고, 마지막 전송이 끝나는 곳으로부터 1초간 4개의 데이터 전송이 이루어졌다.

이러한 방식으로 막대 하나하나 검사하면 각 변화 시점에서 데이터 전송량을 알 수 있다.

 

 

그림에서 1초만 떼어내서 확인하면 다음과 같다.

1초를 간격으로 확인하였을 때, 그림으로 표현

시작 및 끝 지점에 끝나는 막대가 있다면 이는 동시에 데이터 전송이 이루어 지는 경우이지만,

시작 및 끝 지점 + 1에 시작하는 막대가 있다면 이는 동시에 데이터 전송이 이루어 지는 경우가 아니다. (1s 구간을 벗어난 것이다.)

 

 

위의 그림을 수식으로 표현하면 다음과 같다.

1. 시작 및 끝 지점
(전송 도착 시간) >= (시작 및 끝 지점 시간)
2. 시작 및 끝 지점 + 1
(전송 시작 시간) < (시작 및 끝 지점 시간+ 1)

==> {(전송 도착 시간) >= (시작 및 끝 지점 시간) } and {(전송 시작 시간) < (시작 및 끝 지점 시간+ 1)}

 

마지막으로, 배열을 순회하며 데이터 전송 처리량의 최댓값을 구하는 방식을 사용하였다.

max_n = 0
    for i in range(len(time_list)) :
        n1 = 0
        n2 = 0
        s1 = time_list[i][0]
        e1 = time_list[i][0]+1
        s2 = time_list[i][1]
        e2 = time_list[i][1]+1
        for j in time_list:
            if j[1] >= s1 and j[0]<e1 :
                n1 += 1
            if j[1] >= s2 and j[0]<e2 :
                n2 += 1

        if max([n1,n2]) > max_n :
            max_n = max([n1,n2])

 

 

3. 최종 코드

def solution(lines):
    # [start_time, end_time]
    time_list = []
    for i in lines :
        tmp = i.split()
        long_time = float(tmp[2][:-1])-0.001
        time = tmp[1].split(':')
        second = round(float(time[2])-long_time,3)
        minute = int(time[1])
        hour = int(time[0])
        start_time = 60*60*hour + 60*minute + second
        end_time = 60*60*hour+ 60*minute+ round(float(time[2]),3)
        time_list.append([start_time,end_time])
        
    max_n = 0
    for i in range(len(time_list)) :
        n1 = 0
        n2 = 0
        s1 = time_list[i][0]
        e1 = time_list[i][0]+1
        s2 = time_list[i][1]
        e2 = time_list[i][1]+1
        for j in time_list:
            if j[1] >= s1 and j[0]<e1 :
                n1 += 1
            if j[1] >= s2 and j[0]<e2 :
                n2 += 1

        if max([n1,n2]) > max_n :
            max_n = max([n1,n2])

    return max_n

 

 

확실히 3단계를 오니까 문제푸는 시간이 늘어난 것 같다..

(다른 할 일들을 해치지 않도록 시간 분배를 잘해야할 것 같다.. )

급하게 생각하지 말고, 차근차근 해나가는 연습을 해야겠다.💪