2018 KAKAO 코딩테스트 추석 트래픽

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

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

 

초당 최대 처리량을 구하는 문제이다. "단, 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다." 라고 하니, 처리 중인 요청들도 개수를 세야한다.

나는 sliding window 를 사용했다. 
시작지점, 종료지점을 한 list에 넣어두고 (이때, 시작지점, 종료지점 표시) 정렬 한 뒤, 2개의 pointer를 조금식 옮겨가면서 초당 처리량을 구하였다. 앞의 pointer는 window의 시작지점, 뒤의 pointer는 window의 종료지점이다.

이때, 종료 지점을 옮길 때는 최대한 옮길 수 있는 만큼 옮겼다. 즉, (뒤의 pointer가 가리키고있는 시간) - (앞의 pointer가 가리키고 있는 시간) < 1s 를 만족하는 가장 큰 시간의 위치로 옮겼다.

내 풀이의 시간복잡도는 $$ O(n log n) $$ 이다.

 

 

이번에 제출한 코드이다

def parse(log):
    time  = log.split(' ')[1:]
    h,m,s = time[0].split(':')
    s, ms = s.split('.')
    t     = (int(h)*3600 + int(m)*60 + int(s))*1000 + int(ms)
    
    d = int(float(time[1][:-1])*1000)
        
    return t, d
    

def solution(lines):
    answer = 0
    t_list = []
    s_list = []
    for l in lines:
        t,d = parse(l)
        t_list.append((t,1))      #종료
        t_list.append((t-d+1,-1)) #시작
    
    t_list.sort()
    s = e = cnt = 0
    
    print(t_list)
    while s < len(t_list):

        while True:
            if e >= len(t_list):  break
            if t_list[e][0] - t_list[s][0] >= 1000:  break
            if t_list[e][1] == -1: cnt += 1
            e += 1
                        
        if cnt > answer : answer = cnt
        if t_list[s][1] == 1: cnt -= 1
        s += 1
        
    return answer

(다 풀고 다른 사람의 풀이를 봤는데, 1등 코드는 어려운 인덱스 처리를 간단한 트릭으로 편리하게 만들었다.)

 

지난번에 제출했던 코드이다.

코드를 보니 데이터의 크기가 2000으로 매우 작아 O(n^2) 알고리즘을 사용할 수 있다고 생각하여 각 time마다 비교하는 방식으로 짠 것 같다.

def parser(line):
    splited = line.split(' ')

    end_time = splited[1]
    exceed_time = splited[2].replace('s','')
    exceed_time = int(float(exceed_time)*1000)

    time = end_time.split(':')
    seconds = time[2].split('.')

    end = (int(time[0])*3600 + int(time[1])*60 + int(seconds[0]))*1000 + int(seconds[1])
    #print(time[0], time[1], seconds[0])
    start = end - exceed_time + 1

    return [start, end]


def solution(lines):
    answer = 0

    timestamp = []

    for line in lines:
        timestamp.append(parser(line))

    for i, stand in enumerate(timestamp):
        include = []
        local_answer = 1 #자기자신
        for j, target in enumerate(timestamp):
            if i == j:
                continue
            if stand[0] >= target[0] and stand[0]  < target[1]:
                local_answer += 1
                include.append(j)
            elif stand[0] - target[1] < 1000 and stand[0] - target[1] >= 0:
                local_answer += 1
                include.append(j)

        answer = max([answer, local_answer])

    return answer

 

실제 시험이라면 두번째 code 처럼 짤 것 같지만, 이번엔 다르게 풀어보고 싶었다.