📖 문제
문제 설명
카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.
이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.
- 셔틀은
09:00부터 총n회t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대m명의 승객이 탈 수 있다. - 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어
09:00에 도착한 셔틀은 자리가 있다면09:00에 줄을 선 크루도 탈 수 있다.
일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.
단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.
입력 형식
셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.
- 0 ＜
n≦ 10 - 0 ＜
t≦ 60 - 0 ＜
m≦ 45 timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이HH:MM형식으로 이루어져 있다.- 크루의 도착 시각
HH:MM은00:01에서23:59사이이다.
출력 형식
콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.
입출력 예
| n | t | m | timetable | answer |
|---|---|---|---|---|
| 1 | 1 | 5 | ["08:00", "08:01", "08:02", "08:03"] | "09:00" |
| 2 | 10 | 2 | ["09:10", "09:09", "08:00"] | "09:09" |
| 2 | 1 | 2 | ["09:00", "09:00", "09:00", "09:00"] | "08:59" |
| 1 | 1 | 5 | ["00:01", "00:01", "00:01", "00:01", "00:01"] | "00:00" |
| 1 | 1 | 1 | ["23:59"] | "09:00" |
| 10 | 60 | 45 | ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] | "18:00" |
🧮 풀이
셔틀 운행 횟수 n이 10 이하, 셔틀 운행 간격 t이 60 이하, 한 셔틀에 탈 수 있는 최대 크루 수 m이 45 이하입니다. 또한 크루가 대기열에 도착하는 시각을 모은 배열 timetable의 길이가 최대 2000으로, 입력의 크기가 크지 않아 반복문을 이용해 접근하였습니다.
1️⃣ timetable 배열을 시간 기준 정렬
먼저, 버스 시각과 크루들의 도착 시각을 정확하게 비교하기 위해 HH:MM을 자연수 형태의 분 형식으로 변경하고 오름차순 정렬합니다.
timetable = timetable
.map((crew) => {
const [h, m] = crew.split(':').map(Number);
return h * 60 + m;
})
.sort((a, b) => a - b);2️⃣ 크루 태우기
셔틀버스가 n회 운행하므로, 반복문을 n번 순회하며 대기 중인 크루들을 탑승시켜 보겠습니다.
셔틀이 도착했을 때, 셔틀보다 일찍 또는 같은 시각에 도착하여 대기 중인 크루들이 몇 명인지 먼저 계산합니다.
for (let i = 0; i < n; i++) {
let waitings = timetable.filter((crew) => crew <= busM).length;
...
}문제의 요구사항이 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하는 것이므로, 콘은 마지막 셔틀을 탑승한다는 것이 문제의 핵심입니다. 따라서 마지막 셔틀인지 아닌지에 따라 로직을 설계합니다.
도착한 셔틀이 마지막 셔틀일 경우, 콘은 반드시 이 셔틀에 탑승해야 합니다. 하지만 해당 셔틀에 정원 m보다 많은 인원이 도착한 경우 콘은 가장 마지막 크루보다 반드시 일찍 도착해야 합니다.
- 대기 중인 크루들이 정원
m보다 많은 경우, 콘은m번째로 도착한 크루의 도착 시각보다 1분 빨리 도착해야 합니다. - 대기 중인 크루들이 정원
m보다 적거나 같은 경우, 콘은 해당 버스 시간에 맞춰 도착하면 됩니다.
if (i === n - 1) {
// 2-1-1. 대기 인원이 정원과 같거나 더 많은 경우
if (waitings >= m) answer = timetable[m - 1] - 1;
// 2-2-2. 대기 인원이 (정원 - 1)보다 적은 경우
else answer = busM;
}도착한 셔틀이 마지막 셔틀이 아닌 경우, 콘은 탑승하지 않고 대기 중인 크루들만 셔틀에 탑승해야 합니다.
- 대기 중인 크루들이 정원
m보다 많은 경우,timetable배열에서 선착순m명의 크루들을 제거합니다. - 대기 중인 크루들이 정원
m보다 적거나 같은 경우, 대기 중인 크루들만 탑승하면 되므로timetable배열에서 대기 중인 크루들을 제거합니다.
else {
// 2-2-1. 대기 인원이 정원보다 많은 경우
if (waitings > m) timetable.splice(0, m);
// 2-2-2. 대기 인원이 정원과 같거나 더 적은 경우
else timetable.splice(0, waitings);
}🌕 전체 코드
전체 코드는 다음과 같습니다.
function solution(n, t, m, timetable) {
// 1. 도착 순서 기준으로 정렬
timetable = timetable
.map((crew) => {
const [h, m] = crew.split(':').map(Number);
return h * 60 + m;
})
.sort((a, b) => a - b);
let answer = 0;
let busM = 9 * 60;
for (let i = 0; i < n; i++) {
let waitings = timetable.filter((crew) => crew <= busM).length;
// 2. 승객 태우기
// 2-1. 마지막 버스인 경우
if (i === n - 1) {
// 2-1-1. 대기 인원이 정원과 같거나 더 많은 경우
if (waitings >= m) answer = timetable[m - 1] - 1;
// 2-2-2. 대기 인원이 (정원 - 1)보다 적은 경우
else answer = busM;
}
// 2-2. 마지막 버스가 아닌 경우
else {
// 2-2-1. 대기 인원이 정원보다 많은 경우
if (waitings > m) timetable.splice(0, m);
// 2-2-2. 대기 인원이 정원과 같거나 더 적은 경우
else timetable.splice(0, waitings);
}
// 3. 다음 버스 계산하기
busM += t;
}
return [
String(parseInt(answer / 60)).padStart(2, '0'),
String(answer % 60).padStart(2, '0'),
].join(':');
}🧪 실행결과
1️⃣ 첫 번째 과정에서, timetable 배열의 map과 sort를 수행하며 각각 , (은 배열의 길이)의 연산이 이루어집니다. 따라서 이 과정은 총 의 시간 복잡도를 가집니다.
2️⃣ 두 번째 과정에서, 총 n번 반복하고, 반복문의 내부에서 filter와 splice 연산에 각각 이 필요하므로 총 의 시간 복잡도를 가집니다.
따라서 이 풀이의 최종 시간 복잡도는 으로 충분히 빠르게 통과되는 시간 복잡도를 가지게 됩니다. 코드를 제출 후 채점하면 다음과 같이 통과하는 것을 확인할 수 있습니다.
