[Python] 프로그래머스 - [1차] 추석 트래픽(Greedy)

◈ 오류 정정 및 피드백 환영

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

 

---

🔎문제 분석

대표적인 Activity Selection Problem으로 Greedy하게 접근하면 된다.

응답완료시간 기준으로 이미 오름차순 정렬되어 있기 때문에 요청이 끝나는 시점을 기준으로 생각하면 어렵지 않다.

예제1을 예시로 들자면 첫 번째 요청이 끝나는 시점인 04.001초부터 1초까지는 05.000초이며, 2번째 요청이 시작하는 시점은 05.001초이다. 따라서 첫 번째 요청만 처리했다고 볼 수 있기에 초당 최대 처리량이 2가 아닌 1인 것이다. 

 

만약 초당 최대 처리량이 2가 되길 원한다면 다음과 같이 첫 번째 요청이 끝나는 시점을 04.002초로 잡아야 한다.

 

초당 처리량을 구하기 위해서는 특정 로그의 끝에서 1초를 세는 구간을 생성한 뒤에 이 구간에 걸쳐있는 처리의 개수를 세면 된다. 예컨대 첫 번째 로그로 생성한 구간에 걸쳐있는 처리는 총 5개이다.

 

역으로 어떤 로그가 해당 구간에 걸쳐있지 않은 경우를 먼저 생각해 보자면 다음과 같이 2가지 경우이다.

• 로그가 끝나고 나서야 해당 구간이 시작 = 로그 끝 < 구간 시작
• 해당 구간이 끝나고 나서야 로그가 시작 = 구간 끝 < 로그 시작

따라서 위 조건을 만족하지 않는 경우의 개수를 세면 된다.

# t: 특정 로그의 끝
# log_ls: 로그의 시작과 끝이 담긴 이중 리스트
i_s, i_e = t, t+999 # 구간의 시작/끝
cnt = 0
for s, e in log_ls:
    if not (e < i_s)|(i_e < s):
        cnt += 1

최종적으로 구하고 싶은 것은 초당 최대 처리량이므로 다른 로그에 대해서도 구간을 생성해 최댓값을 찾으면 된다.

🤦‍♀️유의 사항

처리시간은 시작시간과 끝시간을 포함하기 때문에 1초가 아닌 0.999초를 더해줘야 한다.

예컨대 33.000초부터 1초 동안 처리된 요청의 개수를 세기 위해서는 34.000초가 아닌 33.999초까지 탐색해야 한다.

---

def str_to_time(line):
    _, t, rt = line.split(" ") 
    h, m, s = t.split(":")
    # time to milisecond
    hour = int(h)*60*60
    minute = int(m)*60
    sec = float(s)
    end = (hour+minute+sec)*1000
    runtime = float(rt[:-1])*1000
    start = end - runtime + 1
    return start, end

def solution(lines):
    answer = 1
    log_ls = [list(str_to_time(i)) for i in lines] # log의 시작/끝
    for _, t in log_ls:
        i_s, i_e = t, t+999 # 구간의 시작/끝
        cnt = 0
        for s, e in log_ls:
            if not (e < i_s)|(i_e < s):
                cnt += 1
        if answer < cnt:
            answer = cnt
    return answer