[프로그래머스][카카오] 셔틀버스

문제

셔틀버스의 횟수, 간격, 줄을 기다리는 대기열의 배열이 주어졌을 때 셔틀버스를 탈 수 있는 도착 시각 중 가장 늦은 시각을 구하시오.

문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/17678)

풀이

처음에 문제를 보고 쉽다고 생각이 들었지만 예제를 보니 꽤 어렵게 느껴졌습니다. 풀고나니 쉬운 문제였고 방금 풀었던 기억을 정리해보니 처음에 더 정리해서 풀었다면 빨리 풀었을 거라는 생각이 들었습니다. 우선 처음엔 어떻게 마지막 셔틀을 탈 수 있는 시간을 구할지 생각해보며 string으로 들어오는 timetable을 숫자로 바꾸는 작업을 했습니다. 09:00 와 같이 들어오기 때문에 hour = (timetable[i][0]-'0')*10 + (timetable[i][1]-'0'), minute = (timetable[i][3]-'0')*10 + (timetable[i][4]-'0') 로 변환하여 hour*60+minute값을 priority_queue에 넣어주었습니다.(대기열 순서대로 주어지지 않기 때문에 우선순위큐를 사용했습니다.) 큐에 넣은 다음부터는 셔틀버스에 n-1번 될 때까지 m명 이내의 승객을 태울 수 있도록 했습니다. 콘은 가능한 가장 늦은 셔틀버스를 타고 싶기 때문에 n-1번째 셔틀까지는 해당 셔틀이 출발하는 시각까지 도착하는 m명과 같거나 작은 승객들을 큐에서 빼내서 태웁니다. 이후에 마지막 셔틀일 때가 중요합니다. 만약 마지막 셔틀인데 이미 기다리던 크루들이 다 탔다면(우선순위 큐가 비었다면) 콘은 마지막 셔틀 시간에 맞춰서 가면 탈 수 있습니다. 하지만 아직 기다리는 크루들이 있다면 그 중 m번째 승객이 되어야합니다. 마지막 셔틀을 m-1번째까지 태웠을 때 두가지의 경우가 있습니다. 우선 첫번째는 m-1번째 태운 크루의 도착 시각과 그 다음 기다리는 크루의 도착시각이 같다면 콘은 m-1번째 승객보다 1분 빨리 도착해야합니다. 두번째는 m-1번째 크루 다음의 크루의 도착시각이 마지막 셔틀버스 출발시각보다 늦다면 콘은 해당 셔틀버스 출발시각에 도착하면 됩니다. 마지막에는 숫자로 바꾸었던 시간을 다시 string으로 바꾸어주면 됩니다. 글로 적어보니 (생각보다 더) 간단한... 문제였습니다.

(해설: http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/)

코드

https://github.com/kswim/Algorithm/blob/master/etc/17678.cpp