Level 3 [1차] 추석 트래픽 <KAKAO 2018 BLIND RECRUITMENT> Python3

https://programmers.co.kr/learn/courses/30/lessons/17676?language=python3 

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

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_%5B1차%5D추석트래픽.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def check_slot(start, slots):
    end = start + 1000 - 1
    cnt = 0
    for s in slots:
        if s[0] <= end and s[1] >= start:
            cnt += 1
    return cnt

def solution(lines):
    answer = 0
    slots = []
    for l in lines:
        y, s, t = l.split(" ")
        ss = s.split(":")
        end = int(ss[0])*3600000 + int(ss[1])*60000 + int(float(ss[2])*1000)
        start = end - int(float(t.split("s")[0])*1000) + 1
        slots.append([start, end])
    for s in slots:
        answer = max(answer, check_slot(s[0], slots), check_slot(s[1], slots))
    return answer

---

풀이 과정

이 문제는 모의 시험 시간에 풀지 못했던 문제였다. 그래서 나중에 풀어보았다.

처음에 종이에 예제를 하나씩 적어보며 문제를 이해하고 코드로 표현하려고 시도해봤다.

그리고 작업의 시작 시간과 응답 완료 시간을 시, 분, 초로 표현한 결과를 만들었는데 시간이 2시간이나 흘렀다. 

이후에 초당 최대 처리량을 구하는데 시, 분, 초로 표현한 값을 이용하려고하다 보니 너무 복잡했다.

그래서 다른 사람 풀이를 참고해봤더니 시, 분, 초를 모두 밀리초 단위로 환산한 후 푼 것을 보고 왜 이렇게 생각을 못했지하며 아차 싶었다..

밀리초로 바꿔 푸니 복잡한 시간 계산도 필요없었다.

def check_slot(start, slots):
    end = start + 1000 - 1
    cnt = 0
    for s in slots:
        if s[0] <= end and s[1] >= start:
            cnt += 1
    return cnt

def solution(lines):
    answer = 0
    #slots[i] = i번째 요청 작업의 [시작 시간, 응답 완료 시간]
    slots = []
    for l in lines:
    	#y = "2016-09-15", s = "hh:mm:ss.sss", t = 처리 시간 s
        y, s, t = l.split(" ")
        ss = s.split(":")
        #시 = hh*3600000ms, 분 = h*60000ms, 초 = 1000ms
        end = int(ss[0])*3600000 + int(ss[1])*60000 + int(float(ss[2])*1000)
        #시작 시간 = 응답 완료시간 - 처리 시간 + 1ms
        start = end - int(float(t.split("s")[0])*1000) + 1
        slots.append([start, end])
    #작업의 시작 시간과 응답 완료 시간을 기준으로 1초 동안 처리되는 작업량을 구한다
    for s in slots:
        answer = max(answer, check_slot(s[0], slots), check_slot(s[1], slots))
    return answer
#시간복잡도 = O(n^2) 공간복잡도 = O(n)

---

참고

• 1. 비밀지도 2021/02/09 - [분류 전체보기] - Level 1 [1차] 비밀지도 Python3

Level 1 [1차] 비밀지도 Python3

• 2. 다트게임 https://hwayomingdlog.tistory.com/45

Level 1 [1차] 다트게임 Python3

• 3. 캐시 2021/02/09 - [코테 노트/프로그래머스] - Level 2 [1차] 캐시

Level 2 [1차] 캐시

• 4. 셔틀버스 https://hwayomingdlog.tistory.com/105

Level 3 [1차] 셔틀버스 Python3

• 5. 뉴스 클러스터링 2021/02/09 - [코테 노트/프로그래머스] - Level 2 [1차] 뉴스 클러스터링

Level 2 [1차] 뉴스 클러스터링

• 6. 프랜즈 4블록 2021/02/09 - [분류 전체보기] - Level 2 [1차] 프랜즈 4블록

Level 2 [1차] 프랜즈 4블록

•