[프로그래머스] 추석 트래픽, Python3

문제는 여기!

입력된 문자열을 시, 분, 초로 파싱하는 것, 각 초 구간의 처리량을 얼마나 효율적으로 분석하냐가 관건인 문제였다.

• 제한사항 및 주의사항
  • lines 리스트의 크기는 2,000개 까지다.
  • S = 응답 완료 시간, 2016-09-15 hh:mm:ss.sss 형식
    • 2016-09-15는 필요 없다.
  • T = 처리시간, 0.1s, 2s, 2.0s 등의 형식으로 주어진다.
  • 문제에서 나온 예시 처럼 '2016-09-15 03:10:33.020 0.011s'는 03:10:33.010 ~ 03:10:33.020 동안 이뤄진 것이다. 시작시간과 응답 완료 시간을 포함하는 것에 유의하자.
    • 시작시간 = S - T + 0.001s
• 풀이전략
  • lines를 시작시간, 응답 완료시간으로 분해하자.
    • lines[i]를 split하기
      • 0번째 : 추석날짜, 1번째 : 응답 완료 시간, 2번째 : 처리 시간
        • 2번째인 처리 시간을 소숫점이 있을 경우, 없을 경우를 나눠서 처리해야한다.
          • 소숫점이 있는 경우 : split(".")해서 초단위인 s를 제외하기
          • 소숫점이 없는 경우 : s를 제외한 문자열을 list로 만든 다음, ["0"]을 추가해주자. 소숫점이 있는 경우처럼 바꿔준다.
    • 시간 계산을 위해 datetime 모듈을 사용했다.
      • datetime.datetime : 날짜와 시간 정보를 모두 담고 있는 객체이다.
        • fromisoformat : 날짜+시간의 iso 포맷의 문자열을 date 타입으로 리턴해준다.
      • datetime.timedelta : 밀리세컨즈까지 지원하는 객체이며, date, datetime 타입의 시간연산을 진행할 수 있는 객체이다.
    • 리스트에 [시작 시간, 응답 완료 시간]을 담고 리턴
  • 이제 1초간 응답 처리량을 구해보자
    • 일단, 모든 구간을 살펴보기에는 2,000(lines의 크기) * 2(시작, 종료시간) * 60(초) * 1,000(millisecond) * 60(분) * 60(시) = 864,000,000,000 이렇게 하지말자 쉬먀
    • 우리가 구한 리스트에서 시작시간 ~ 0.999초, 응답 완료 시간 ~ 0.999초 구간 동안 겹치는 트래픽을 찾아 그 최댓값을 반환하면 된다. O(2,000 * 2 * 2,000)
    • 1초가 아닌 0.999초의 범위를 설정한 이유는 코드 밑에 설명하겠다.

import datetime


def get_times(lines):
    result = []
    for line in lines:
        data = line.split()
        date = str(data[0]) + " " + str(data[1])

        if '.' in data[2]:
            delay = data[2].split(".")
            delay[1] = delay[1][:-1]
        else:
            delay = list(data[2][:-1])
            delay += ['0']

        end = datetime.datetime.fromisoformat(date)
        start = end - datetime.timedelta(seconds=int(delay[0]), milliseconds=int(delay[1]) - 1)

        result.append([start, end])
    return result


def compare(point, target):
    start = point
    end = point + datetime.timedelta(milliseconds=999)

    if target[0] <= start <= target[1]:
        return True
    if target[0] <= end <= target[1]:
        return True
    if start <= target[0] <= end and start <= target[1] <= end:
        return True
    # if start <= target[0] <= end:
    #     return True
    # if start <= target[1] <= end:
    #     return True
    # if start <= target[0] <= end and start <= target[1] <= end:
    #     return True

    return False


def solution(lines):
    answer = []
    times = get_times(lines)
    for time in times:
        for t in time:
            count = 0
            for target in times:
                if compare(t, target):
                    count += 1

            answer.append(count)

    return max(answer)

내가 실수한 곳이 두 군데가 있다.

1. 구간 나누기

   • 처음에 start + 1초의 범위를 설정했지만 틀렸다. 결국 다른 분들의 코드를 보고 이해할 수 있었다.
     • 문제에서 소요시간은 시작시간과 작업 완료 시간을 포함한다.
     • start + 0.999초로 구간을 잡아야 문제에서 원하는 기준에 부합하는 범위라고 할 수 있다.
     • '작업1'을 기준으로 했을 때, 1초에서 시작했으면 1.999초에 끝난다. 만약 1초~2초였다면 작업2가 해당 범위에 포함되므로 원하는 답을 도출할 수 없다.
   

2. 시간 비교

   • target 안에 start가 있어야 한다.
   • target 안에 end가 있어야 한다.
   • start와 end 안에 target이 있는 경우

   나는 주석처리한 코드를 보면 알 수 있듯 target 시점이 start와 end 안에 있어야 되는 거로 착각해서 테스트 케이스 일부가 틀렸었다.