[프로그래머스] 추석 트래픽 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

 

반나절동안 씨름해서 겨우 풀었다.

풀고보니 생각보다 간단했다.

 

처음 시도한 알고리즘은 슬라이딩 윈도우로 푸는 것이었다.

 

응답시간과 처리시간이 주어지므로 시작시간과 완료 시간을 구할 수 있다.

이 지점을 배열에 표시하고 처음부터 1초 간격으로 개수를 세주고 했다.

 

배열의 최대 길이가 1000*60*60*24이므로 될 줄 알았다.

시간을 밀리초로 변환 했으므로 윈도우 사이즈는 1000이다. 윈도우를 움직이면서 그 사이의 개수를 세주어야하는데 이과정에서 시간초과가 나는 듯했다.

오른쪽에서 들어오면 +1, 왼쪽으로 나가면 -1 하는 방식으로 하기도 하고, 로그마다 잘 구분줘서 다르게하기도 하고, 배열이 크기가 크므로 딕셔너리로 필요한 부분만하기도 하고 이런저런 방법 다 해봤지만 3,18번 예제에서 시간초과가 계속 났다.

 

 

그래서 처음부터 다시 고민해봤다.

정보는 오름차순으로 주어지고, 이를 (시작시각, 종료시각)으로 변환해서 저장하면 종료시각으로 오름차순 정렬이 된다.

시작지점이나 종료지점을 반드시 하나 이상 포함해야 최대가 된다. 그래서 나는 종료시각을 기준으로 1초간의 요청을 생각했다.

 

현재 지점의 종료시각과 다음 지점의 시작시간을 봐보자.

정보는 오름차순으로 정렬되어 있으므로

(현재지점 종료시각) >= (다음 지점 시작시각) 이라면 현재지점의 종료시각에 다음 지점의 응답은 동시에 처리되는 것이다.

 

즉 아래처럼 되어 있는 것이다.

ㅣ-------------ㅣ

        ㅣ----------------ㅣ

 

또한 다음 지점의 시작시각이 현재지점 종료시각 보다 크더라도 그 차이가 1초가 안된다면 1초 동안 함께 처리될 수 있는 요청이다.

ㅣ----------ㅣ

                (간격 0.5초)ㅣ----------ㅣ

따라서 한 로그의 종료시각을 기준으로 그 다음 모든 로그에 대해서 위의 경우를 세주면 된다.

종료시각부터 1초 구간으로 잡아서 이전 로그는 볼필요가 없다.

주의 할점으 위의 두 경우가 아니라고 해서 반복문을 종료하면 안된다. 왜냐면 종보는 종료시각을 기준으로 정렬되어 있기 때문이다. 그래서 모든 로그를 다 확인해야한다.

 

그래서 n^2의 시간으로 풀이 할 수 있었다.

 

def solution(lines):
    global min_millisec,targets
    targets = []

    min_millisec,min_t = time_to_millisec(lines[0])

    for line in lines:
        millisec,t = time_to_millisec(line)
        calc_start_end(millisec,t)

    answer = 1

    for i in range(len(targets)-1):
        tmp = 1
        for j in range(i+1,len(targets)):
            if targets[i][1] >= targets[j][0]:
                tmp += 1
            elif targets[i][1] + 999 >= targets[j][0]:
                tmp += 1
        answer = max(answer, tmp)

    return answer

def calc_start_end(millisec,t):
    start = millisec - min_millisec - t + 3001
    end = millisec - min_millisec + 3000

    targets.append((start,end))
def time_to_millisec(line):
    line = line.split()
    millisec = line[1]

    ms = int(millisec[9:])
    s = int(millisec[6:8]) * 1000
    m = int(millisec[3:5]) * 1000 * 60
    h = int(millisec[:2]) * 1000 * 60 * 60
    millisec = ms + s + m + h

    t = int(float(line[2][:-1]) * 1000)

    return millisec,t