[KAKAO] 추석 트래픽 (2018 KAKAO BLIND)

프로그래머스의 카카오 문제들은 구현 난이도가 높고, 문제가 깔끔하다고 생각해서 몇 번을 풀 예정이었다.

어려웠던 문제는 한 3~4번 정도 풀어볼 예정이다.

 

백준에서 문제를 풀다가 다시 넘어와서 프로그래머스 문제들을 다시 풀어보면서 옛날의 코드들과 비교해봤다.

대부분 문제들에서 옛날에 짠 코드들보다 개선되었음을 느꼈지만, 몇몇 문제들은 예전의 코드들이 낫기도 했다.

 

쉬웠던 문제들은 파이썬에 슬슬 적응 해 가면서 푸는 속도가 올라간 것 같지만, 어려운 문제들은 생각하는 데

똑같이 시간이 걸리긴 했다.

 

이번 문제는 디버깅이 좀 어려웠던 것 같다. 문자열에서 숫자로 바꾼 뒤, 크기를 비교하려 했지만 하나하나 비교하려다 보니 눈

빠지는 줄 알았다... 디버깅 하면서 알아낸건 문제를 잘못 읽은 것을 알게되었다,,,,

입력을 끝나는 시간을 줘 버리면 어떡합니까 ,, 글쓴이는 시작시간을 준 줄 알고 열심히 풀었다..

 

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

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

첫번째 이 문제를 풀다가 고생했던 것은 float 때문이다. float+float 를 하다가 잘 못된 값이 나오는 것을 알았다.

부동 소수점의 덧셈과 뺄셈은 우리가 알았던 방식과는 사뭇 다른 것 같다.

 

그렇기 때문에 1000을 곱한 뒤 int형으로 바꾸어 로직을 짰다.

 

1. 시작시간과 끝나는 시간을 int 형으로 바꾸어 새 배열에 담는다. 

- int형으로 바꾸라는 것은 해당 시간들을 가장 작은 단위인 '초'를 기준으로 나타내라는 것이다.

 

2. (1초)에 해당하는 시간에 얼마나 트래픽이 있는지 생각해본다.

 

아마 2번의 로직을 짜는 데에서 시간이 오래걸렸을 것이라 생각한다.

 

처음에는 투포인터적인 생각을 통해 1000 단위를 수시로확인 하려고 했지만, 86,400,000 초를 순회한다는 것은 뭔가 잘못된것 같아

다른 생각을 해보았다. 그리디라 해야하나 잘 모르겠지만 정렬을 통해 해결했다.

 

먼저 시작순으로 정렬하면 다음과 같은 그림이 나온다.

 

정답이 5개 인 것은 금방 알 수 있다.

 

5번의 시작점부터 연두색의 부분까지 모든 구간이 가능하다.

 

한 가지 생각이 들었는데, 가장 많은 트래픽을 포함하는 구간은 마지막 트래픽의 시작점까지 샐 수만 있다면, 가능하다. 

< 사실 이 말을 어떻게 표현해야 할 지 모르겠음... >

 

각 트래픽을 순회하면서 시작점 기준으로 1초 전 을 limit으로 잡아.

이 전 트래픽들을 보며 구간에 포함되는 것들의 개수를 세주었다.

 

def solution(lines):
    answer = 0
    traffic = []
    def change_clock(c):
        hour, minute, second = map(float, c.split(':'))
        total = 1000*(hour*3600 + minute*60 + second)
        return int(total)
    
    for line in lines:
        li = line.split()[1:]
        clock, t = li
        time = int(float(t[:-1])*1000)-1
        end = change_clock(clock)
        if time < 3000: start = end - time
        else: end = start - 2999
        traffic.append((start, end, clock, t))
        
    traffic = sorted(traffic)
    t_len = len(traffic)
    
    for i, tr in enumerate(traffic):
        s, e,a, b = tr
        limit = s - 999
        cnt = 1
        
        for j in range(i-1, -1, -1):
            next_s, next_e, c,d = traffic[j]
            if next_e >= limit:
                cnt += 1

        if cnt > answer:
            answer = cnt
    
    return answer