2018 카카오 코딩테스트 1차 셔틀버스 JS 문제풀이

🔗직접 문제 풀러가기

 

 

 

 

문제

 

콘이 셔틀을 타고 사무실로 갈 수 있는 정류장 도착 시각 중 제일 늦은 시각을 구하여라

 

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.
• 모든 크루는 잠을 자야 하므로 23:59에는 집에 돌아간다.
• 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다.

 

입력값

 

셔틀 운행 횟수 n,

셔틀 운행 간격 t,

한 셔틀에 탈 수 있는 최대 크루 수 m,

크루가 대기열에 도착하는 시각을 모은 배열 timetable.

 

• 0 ＜ n <= 10
• 0 ＜ t  <= 60
• 0 ＜m <= 45
• 0 < timetable.length <= 2000

 

 

출력값

 

• 도착 시각은 HH:MM 형식의 문자열이며, 00:00에서 23:59 사이의 값이 될 수 있다.

 

 

 

 

문제풀이

 

1. timetable에 대한 전처리를 하여 변수 crews에 저장한다.

• '09:00'형식의 원소들을 분을 나타내는 숫자로 컨버팅
• 마지막 버스가 도착한 이후에 온 크루들을 제외
• 남은 크루들을 역순으로 정렬

2. 버스가 도착하는 횟수인 n번 순회한다. 각 이터레이션을 회차라고 하겠다.

 

3. 매 회차마다 태울 수 있는 크루의 수(<= m)만큼 순회한다.

• 태울 수 있는 크루들을 배열 crews에서 삭제한다.
• 각 크루를 배열에서 삭제하는 동시에 콘의 승차시간도 업데이트한다.
• 만차일때는 마지막 크루보다는 빨리 도착해야 버스에 탈 수 있으므로 1초먼저 도착해야한다.
• 크루가 버스도착시간보다 늦게 도착했으면 순회를 멈추고 다음 회차로 넘어간다.
• crews 배열이 텅 빈 경우 바로 리턴한다. 이는 모든 크루가 버스에 탓거나 마지막 버스보다 늦게 도착할 예정인 것이므로 콘은 그냥 마지막 차가 도착할시간에 맞춰서 버스를 타면 된다.

 

 

a = timetable.length

시간복잡도: O(a log a)

공간복잡도: O(a)