[프로그래머스] 추석 트래픽 (python/파이썬)

1. 키워드

최대, 최소, 경우의 수 등을 찾는 유형은 완전탐색, 다이나믹 프로그래밍, 그리디 알고리즘 등 여러가지 방법으로 해결할 수 있다. 그러나 문제의 맨 아래부분의 그림을 살펴봤을 때, 그리디 알고리즘의 유형 중 하나인 task schedulling problem 유형과 굉장히 비슷함을 알 수 있다. 또한, 입력으로 주어지는 데이터가 오름차순으로 정렬되어 있기 때문에, 정렬과 밀접한 관계를 갖는 그리디 알고리즘으로 접근하는 것이 좋을 것 같다고 생각을 했다.

2. 접근 방법

1) 먼저 입력으로 들어오는 logs 배열을 살펴본다. logs 배열의 log들은 일정한 고정된 타입의 문자열 형태의 시간이다. 문자열 형태의 시간은 카카오 문제들의 특성으로, 대소 비교를 하기 위해서는 우선 정수형으로 변환해 주어야 한다.

# 정수형으로 시간을 변환하는 코드
def get_time(time):
    hour = int(time[:2]) * 3600
    minute = int(time[3:5]) * 60
    second = int(time[6:8])
    millisecond = int(time[9:])
    return (hour + minute + second) * 1000 + millisecond

2) 정수형으로 변환시킨 시간은 끝나는 시간으로, 시작 시간도 같이 구해준다.
시작 시간을 구하는데 주의해야 할 점은, 끝나는 시간과 시작 시간을 모두 포함하기 때문에, 문제에서 나와있는 형태로 시작 시간과 끝나는 시간을 구하기 위해서는 끝 시간에서 구한(get_time(time)) 시간에 duration_time을 빼준 값에 1을 더해야 한다.

구한 시작 시간과 끝나는 시간을 각각 다른 배열에 추가해준다. 여기서는 start_time과 end_time 배열에 각각 추가해 주었다.

# 시작 시간을 구하는 코드
def get_start_time(time, duration_time):
    n_time = duration_time[:-1]
    int_duration_time = int(float(n_time) * 1000)
    return get_time(time) - int_duration_time + 1

3) start_time 배열과 end_time 배열의 요소들을 순회하며 대소를 비교한다. 이때 end_time 배열의 요소들은 정렬되어 있음을 보장받기 때문에, end_time 배열을 기준으로 대소를 비교한다.

주어진 구간에서 최대, 최소를 구하는 방법은 여러가지가 있지만, 이 문제에서는 임의의 시간에서 1000밀리초 구간에서 쿼리가 존재하기만 하더라도 처리된 것으로 처리하기 때문에, 단순히 겹치는 것만 확인하여 겹친다면 카운트를 1 증가시키면 된다. 1000 밀리초 떨어진 것을 어떻게 처리하면 좋을까?

start_time[j]를 1000 밀리초 앞으로 당겼을 때, end_time[i]보다 작다면 1000 밀리초 내에 처리된 것으로 생각할 수 있다.

이 때, 주의해야 할 점은 조건이 end_time[i] <= start_time[j] - 1000이 아닌, end_time[i] < start_time[j] - 1000라는 것이다.
처리시간은 시작시간과 끝 시간을 모두 포함하기 때문에, 끝시간에서 생각한다면 999 밀리초 이내에 같은 작업이 끝남과 동시에 시작된다면 초당 처리시간이 증가하게 되는것이다. 따라서 start_time[j] - 1000이라면 end_time[i]보다 작아야 초당 처리시간이 증가하게 된다.

# python 코드
def solution(lines):
    answer = 0
    start_time = []
    end_time = []

    for t in lines:
        time = t.split(" ")
        start_time.append(get_start_time(time[1], time[2]))
        end_time.append(get_time(time[1]))
    for i in range(len(lines)):
        cnt = 0
        cur_end_time = end_time[i]
        # i번째는 현재 자신의 시작시간이고, i 이하는 그 이전의 시작시간이므로 카운트 할 필요가 없다.
        for j in range(i, len(lines)):
            if cur_end_time > start_time[j] - 1000:
                cnt += 1
        answer = max(answer, cnt)
    return answer


def get_time(time):
    hour = int(time[:2]) * 3600
    minute = int(time[3:5]) * 60
    second = int(time[6:8])
    millisecond = int(time[9:])
    return (hour + minute + second) * 1000 + millisecond


def get_start_time(time, duration_time):
    n_time = duration_time[:-1]
    int_duration_time = int(float(n_time) * 1000)
    return get_time(time) - int_duration_time + 1

새 블로그 바로 가기

new Blog