[algorithm] 2018 Kakao Blind Recruitment 1차 - 셔틀버스

1. 문제

 

https://programmers.co.kr/learn/courses/30/lessons/17678#

코딩테스트 연습 - [1차] 셔틀버스

 

2. 풀이

 

def timer(timestr):
    timearr=timestr.split(":")
    return int(timearr[0])*60+int(timearr[1])
def strtimer(timeint):
    li  =[str(timeint//60).rjust(2,"0"),str(timeint%60).rjust(2,"0")]
    return ":".join(li)

def solution(n, t, m, timetable):
    #마지막 버스는 몇시인가
    lastbus  = 9*60+(n-1)*t
    # 버스를 모두 저장하자
    bustime = [9*60+i*t for i in range(n)]
    #한 버스에 탈 수 있는 사람은 m 명이다.
    #사람들이 어떤 시간 구간에 왔는지를 확인하자
    group =[ [] for i in range(n)]
    idx =0
    timetable_sorted=sorted(timetable)
    for i in range(len(timetable_sorted)):
        x=timer(timetable_sorted[i])
        while True:
            if idx>=n : break
            
            if x>bustime[idx]  :
                idx+=1
            else: break
            
        if idx>=n:
            break
        group[idx].append(x)
    cur=0
    queue=[]
    for x,y in zip(bustime,group):
        # queue 는 이전시간대에 와서 못탄사람 + 이번 시간대에 온사람
        queue.extend(y)
        ## 기존에 온사람을 다 채워도 남는다면, 버스 출발시간 맞춰서 타면 됨
        if len(queue)<m:
            cur=x
            queue =[] # 다 찼으니 큐는 비운다.
        # 기존에 온사람들로 다 차버린다면
        else:
            #제일 뒤에 탑승 성공한 사람보다 1초 빨리 탈 수 있어야함.
            cur=queue[m-1]-1
            queue =queue[m:]

    return strtimer(cur)

 

3. lessons

로직을 꼼꼼하게 체크해야 풀 수 있는문제였다.

나는 시간대별로 도착한 사람을 나눠서 큐에 추가해줬는데 그냥 한줄로 쭉 처리했으면 더 간단했을 것 같다.

최종 정답출력시 strtimer 라는 함수를 따로 만들어서 수행했는데 zfill을 사용했으면 더 쉽게 구현할 수 있었다. 

 

str(temp//60).zfill(2) + ":" + str(temp%60).zfill(2)

 

 

4. 후기

상당히 고생했던 문제다. 로직이 맞다고 생각했는데도 70퍼센트대 정답률이 나와서 많이 해멨다.

작년에 풀다가 포기했었는데, 결국 하나하나 주석 달면서 로직을 확인해보기로했다

결과적으로 인덱스를 꼼꼼하게 체크하지 못해서 실수를 했던거였다.

queue를 처리하고서 다음 루프로 넘어갈 때 queue =queue[m:] 로 해야되는 queue[m=1]  로 쓰기도 했고..

제일 뒤에 탑승한사람에서 -1 을 해야되는데 제일 앞에 탑승한 사람에서 -1을하고..

결과적으로 문제를 정확히 이해하지 못했던 셈이다.

앞으로 더 문제 풀때 집중해야겠다.

 

 

=> 카카오 2018 1차 문제 풀이 완료

https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/