추석 트래픽 (17676번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 추석 트래픽 (17676번)

 

난이도 : Lv 3

알고리즘 : Priority Queue (우선순위 큐), Sorting (정렬)

Time Complexity : O( N * logN )

 

from heapq import heappop, heappush


def solution(lines):
    se = []
    for line in lines:
        _, end, t = line.split()
        h, m, s = map(int, end[:8].split(':'))
        end = int(end[-3:])
        end += 1000 * (h*3600 + m*60 + s)
        start = end - int(1000*float(t[:-1])) + 1
        se.append((start, end))
    se.sort()
    
    pq = []
    cnt = maxy = 0
    for s, e in se:
        while pq and pq[0] <= s-1000:
            heappop(pq)
            cnt -= 1
        heappush(pq, e)
        cnt += 1
        maxy = max(maxy, cnt)
    return maxy

 

우선순위 큐와 정렬을 활용하는 문제이다.

 

(sorting)
1. 로그를 응답시작시간 기준으로 정렬한다.

 

(priority queue)
2. 로그를 앞에서부터 하나씩 탐색한다.

2-1. 현재 우선순위 큐에 남아있는 값 중,
현재 로그의 응답시작시간보다 1초 이상 빨리 끝난 값들은 삭제한다.

2-2. 현재 로그의 응답종료시간을 우선순위 큐에 넣는다.

2-3. 현재 우선순위 큐의 길이 (cnt) 를
역대 우선순위 큐의 최고 길이 (maxy) 와 비교한다.

현재 길이 (cnt) 가 더 길다면,
역대 우선순위 큐의 최고 길이를 (maxy)
현재 우선순위 큐의 최고 길이로 갱신한다. (maxy = cnt)

 

3. 모든 로그를 확인한 후, 최종적으로 maxy를 return 한다.