[프로그래머스] 추석 트래픽 (Python, Level3)

 

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

아이디어

일단 string에 대한 처리를 해주어야한다. 로그 기록이 하루치기에 input으로 주어지는 9월 15일이라는 정보는 중요하지 않다. 시간이 주어지고, 처리시간이 주어지는데  최소 단위인 ms로 통일을 시켜서 풀었습니다.

조금 생각을 내려놓고 풀었을 때,  start를 기준으로 하건 end를 기준으로 1초 간격내의 쿼리를 탐색하는 완전탐색도 분명 가능하다. ( N=2000 밖에 안되므로 ) 이렇게 하면 자신이 기준을 잡은 start or end를 기준으로 1000ms이내의 쿼리들을 검색해야하고, 코드도 난잡해지고 경우의수도 나눠야 할거라고 생각했다. 어떤 start와 end가 끝자락에서 겹치는 문제 등등 ..

 

그래서 나는 start를 기준으로 잡고 start와 쿼리 처리가 겹치는 쿼리를 탐색하기 위해 start를 -999ms 해주었다.

이렇게 각 쿼리의 start를 왼쪽으로 1초 늘려줘서 추후 계산 없이 괄호를 여닫듯, 아래 강의실 배정 문제처럼 강의실을 또 여닫든 ( depth가 계속 파고들어 가진다고 생각하자 ) 그런식으로 카운팅만 해주면 되는 것이다.

11000번: 강의실 배정

 

코드 풀이

MAX_END = 86400999 # 23:59:59.999 0.1s
def solution(lines):
    line_lists = []
    for line in lines:
        date, time, t =line.split()
        #문제의 최소단위인 ms로 변환해서 풀이.
        ms = 0
        ms += int(time[:2])*60 * 60 * 1000 # 시간 * 분(60) * 초(60) * ms(1000)
        ms += int(time[3:5]) * 60 * 1000
        ms += int(time[6:8]) * 1000
        ms += int(time[9:])
        t = t[:-1]
        t = float(t)*1000
        t = int(t)
				
        # start지점을 1초만큼 왼쪽으로 보내줍니다.
        # 다만, 이때도 시작시간이 포함되므로 -1000이 아닌 -1000+1을 계산합니다.
        start = max(0,ms-t+1-999)
        end = ms
        # end를 기준으로 하는 풀이도 가능합니다.
        # start = ms-t+1
        # end = min(MAX_END, ms+999)

        line_lists.append((start,False))
        line_lists.append((end,True))
    
    line_lists.sort()
    max_count = 0
    count = 0
    for i,line_list in enumerate(line_lists):
        # start라면 1을 더하고, end면 1을 감소시키면서 count의 최댓값을 갱신합니다.
        if line_list[1] == False:
            count += 1
        else:
            count -= 1
        max_count = max(max_count, count)
    return max_count