본문 바로가기
Problem Solving/프로그래머스

추석 트래픽 / 레벨3

by ggyongi 2022. 5. 10.
반응형

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

 

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

입력: [ "2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s", "2016-09-1

programmers.co.kr

import re
import heapq
def solution(lines):  
    info = []
    min_start = 9876543210
    max_finish = -1
    
    for line in lines:
        date, finish, time = line.split(' ')
        
        hh, mm, ss, sss = map(int, re.split('[:.]', finish))
        mm += hh*60
        ss += mm*60
        sss += ss*1000
        finish = sss
        
        time = int(float(time.split('s')[0])*1000)
        start = finish - time + 1
        
        if start <0: 
            start = 0
        
        min_start = min(min_start, start)
        max_finish = max(max_finish, finish)
        
        heapq.heappush(info, [start, finish])
               
    answer = 0
    t = min_start
    box = []
    box_count = 0

    while t < max_finish+1:
        
        while info and info[0][0] <= t+999:
            log_start, log_finish = heapq.heappop(info)
            heapq.heappush(box, log_finish)
            box_count += 1
        
        answer = max(answer, box_count)
        
        while box and box[0] == t:
            heapq.heappop(box)
            box_count -= 1
        
        if info and box:
            t = min(info[0][0], box[0])
        elif info:
            t = info[0][0]
        elif box:
            t = box[0] 
        else:
            break
        
    return answer

일단 모든 로그를 훑으며 시작시간(start)와 종료시간(finish)를 구해준다.

이때 min_start, max_finish를 추가로 찾아주어 이후 탐색의 범위를 줄인다.

 

이 문제에서는 힙 자료구조가 결정적인 역할을 한다.

info에는 [시작시간, 종료시간] 형태로 데이터가 들어가 있다.

 

시간을 의미하는 t는 min_start에서부터 시작하도록 해주면 된다.(t는 밀리세컨드 단위!)

반복문 속에서 우선 info를 살펴보며 필요한 데이터를 box 안으로 넣어주는 작업을 한다.(힙으로 빼서)

여기서 필요한 데이터란 현시각 t로부터 1초 안의 범위인 t+999까지 안에 시작시간이 포함되는,

즉 쉽게 말해 1초 구간 속에서 시작하는 로그다.

이들은 전부 카운트가 되어야 하므로 box_count 값을 1올려준다.

 

그렇게 구해진 box_count를 answer와 비교하며 답을 구해주면 된다.

근데 이 중 종료시간이 다 된 로그들은 box에서 빼주어야 한다. 이때도 힙 팝으로 빼준다.

 

t는 info, box를 살펴보며 최대한 효율적으로 점프하게 해준다.

 

 

비전공자 네카라 신입 취업 노하우

시행착오 끝에 얻어낸 취업 노하우가 모두 담긴 전자책!

kmong.com

댓글