이번 문제부터는 난이도가 중으로 올라갔습니다. 이번 문제에서 다소 까다롭게 여겨지는 부분은 시간 계산과 규칙 지정입니다. 먼저 규칙부터 지정해 보겠습니다. 버스에 탑승할 수 있는 가장 늦은 시간을 구할 때, 다음과 같은 경우에 항상 해당됩니다.
1) 운행버스에 탑승객이 모두 타지 못하는 경우
2) 운행버스에 1개 이상의 시간대에 온 탑승객이 모두 타는 경우
3가지 경우에서 각각의 최적 시간은 언제일까요? 1번의 경우, 버스와 동시에 오면 항상 탈 수 있고 이게 가장 늦은 시간이 됩니다. 2번째의 경우, 특정 시간대의 사람이 탑승하여 꽉차게 되면, 그 시간대의 사람 -1분에 탑승하면 됩니다. 예를 들어 3명이 탈 수 있는 버스에 09:09, 09:10, 09:10, 09:11 분에 온 탑승객이 있다면, 09:09분에는 와야 됩니다.
규칙을 정립하고, 문제를 쉽게 풀기 위해 숫자로 변경하겠습니다. 원리는 간단합니다. 18:01 분이라면 :를 뺀 나머지를 숫자로 처리하면 됩니다. 위의 경우는 1801이 되겠네요. 이런식으로 모든 사람들의 시간을 숫자로 변경한 후, sort를 진행하여 맨 앞의 사람부터 실제로 버스에 태워보면 됩니다.
단 몇 가지 주의해야 할 상황이 있는데요. 00:00 분이 0이기 때문에 여기서 1분을 빼면 -1이 됩니다. 이럴 때는 2400(24:00) 을 더하여 보정을 하면 됩니다. 또 뒤의 2자리가 60 이상일 경우 시간을 더해줘야 하기 때문에 여기서도 적절한 처리를 해주면 됩니다.
string solve(int n, int t, int m, vector<string> timetable) {
vector<int> cvtTimetable;
for (auto time : timetable) {
int cvt = (time[0] - '0') * 1000 + (time[1] - '0') * 100 + (time[3] - '0') * 10 + time[4] - '0';
cvtTimetable.push_back(cvt);
}
sort(cvtTimetable.begin(), cvtTimetable.end());
int startTime = 900, ans = 0;
for (int i = 0, j = 0; i < n; i++) {
int cm = 0, cmp=0;
map<int, int> timetype;
while (cm < m && j<timetable.size()) {
if (cvtTimetable[j] > startTime) break;
timetype[cvtTimetable[j]]++;
j++;
cm++;
}
if (cm < m) {
ans = max(ans, startTime);
}
else {
int chk = 0;
for (auto it : timetype) {
if (chk + it.second >= m) {
cmp = it.first - 1;
if (cmp % 100 > 59) cmp -= 40;
if (cmp < 0) cmp += 2400;
break;
}
chk += it.second;
}
ans = max(ans, cmp);
}
startTime += t;
if (startTime % 100 > 59) {
startTime += 100, startTime -= 60;
}
}
string cvtans = "";
auto hh = to_string(ans / 100), mm = to_string(ans % 100);
if (hh.length() < 2) hh = "0" + hh;
if (mm.length() < 2) mm = "0" + mm;
return hh + ":" + mm;
}