[프로그래머스] [1차] 추석 트래픽 (2018 카카오 공채)

🔗

풀이

2018년 카카오 공채 7번 문제였고 정답률은 17%였다고 한다. 지금은 좀 올라서 21%이다.

시간문제인데 초에서 끝나는 게 아니라 밀리세컨드까지 고려해야 하기 때문에 모든 경우의 수를 고려하면 3백만을 넘어서 시간초과가 난다. 그래서 그냥 카카오 문제 풀이를 봤는데 요청의 개수가 변경되는 경우는 특정 로그가 시작되거나 끝나는 시간 뿐이라고 한다. 즉 모든 밀리세컨드를 다 고려할 필요 없이 특정 로그가 시작되거나 끝나는 시간만 생각해보면 된다. 어떤 특정 로그가 시작되는 시간에는 1개가 추가될 것이고, 끝나는 시간은 그 이후부터는 1개가 사라질거니까 그 부분들만 고려하면 된다는 것 같았다.

요청 개수 구하기

1초를 기준으로 했을 때 그 사이에 속하는 로그들은 아래의 경우의 수 총 4가지가 있다.

1. 이미 시작했고, 기준 시간 내에 끝나는 경우
2. 기준 시간 내에 시작하는 경우
3. 기준 시간 내에 시작하고 끝나는 경우
4. 기준 시간 이전에 시작해서 기준 시간 이후에 끝나는 경우

4가지의 경우를 다 따로 구하려고 했는데 참고한 블로그를 보니 간단하게 구할 수 있었다. 4개의 공통점을 보면, 끝나는 시간의 경우는 기준 시간 1초의 시작점(파란색)보다 크다. 4개의 시작 시간은 기준 시간 1초의 끝나는 시간(빨간색)보다 작다.

풀이는 이 블로그를 참고했다

def convert(line):
    _, time, plus = line.split()
    h, m, s = time.split(':')
    end = (int(h)*3600+int(m)*60+float(s))*1000
    start = end-float(plus[:-1])*1000+1
    return start, end
    
def solution(lines):
    def process(start):
        cnt = 0
        for line in lines:
            if start<=line[1] and start+999>=line[0]:
                cnt += 1
        return cnt
    
    lines = list(map(lambda x: convert(x), lines))
    
    answer = 1
    print(lines)
    for line in lines:
        answer = max(answer, process(line[0]), process(line[1]))
    return answer

비슷한 문제

• 백준 공주님의 정원