문제설명

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 ‘크루’라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

  • 셔틀은 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|

접근

  • 카카오 문제들의 공통점이지만 문제가 길고 제약조건이 꽤 많기에 조건을 정확하게 캐치하려고 노력했다.
  • 특별히 알고리즘이 필요하다고 느끼진 않았다. 제일 늦은 도착 시간이 관건이었기에 마지막 버스를 중요하게 생각했다.

내가 생각한 풀이

  • 우선 버스를 탈 수 없는 시간을 제외시켰다. 오후 6시 이후 ~ 밤 12시 이전
  • 버스가 올 때 마다 탈 수 있는 사람을 모두 태우기 때문에 vector에서 제거 해당 사람들을 제거해주었다. (말이 좀 이상하네…)
  • 마지막 버스가 올 때 남아있는 사람들로 연산을 하여 가장 늦게 갈 수 있는 시간을 도출해냈다.
    • 내가 선택한 방법은 m만큼 태울 수 있으면 마지막 버스가 도착한 시간을 가장 늦은 시간으로 채택했고 m보다 사람이 많이 있으면 태울 수 있는 마지막 사람의 시간 -1분을 정답으로 채택했다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
//콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.
//콘은 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다.
//하루가 지나면 대기열은 초기화된다.
//즉 n*t보다 timetable의 원소값이 클 경우 이 원소들은 무시해도 된다는 말이다.
//계산해야 할 것은 09:00보다는 값이 크고 09:00 + n*t 보다는 작은 timetable의 원소가 몇 개인지 세어야 한다.
//버스가 떠날때마다 timetable에서 빠질 수 있는 원소는 모두 빼주자.
//그렇게 count를 하다가 마지막 값에 도달하면 그 값이 정답이 될 것이다.
using namespace std;

int string_to_int(string s) // 문자열로 주어진 시간을 int로 변환
{
  string temp_hour = "", temp_minute = "";
  int int_hour = 0, int_minute = 0, int_time = 0;
  int_hour += (s[0] - '0') * 600;
  int_hour += (s[1] - '0') * 60;
  int_minute += (s[3] - '0') * 10;
  int_minute += (s[4] - '0');
  int_time = int_hour + int_minute;
  return int_time;
}
string int_to_string(int n) //int를 다시 문자열로 변환
{
  int hour = n/60, minute = n%60;
  string temp_hour = "0", temp_minute = "0";
  if(hour >= 10)
  {
      temp_hour = "";
      temp_hour = to_string(hour);
  }
  else
  {
      temp_hour += to_string(hour);
  }
  if(minute >= 10)
  {
      temp_minute = "";
      temp_minute = to_string(minute);
  }
  else
  {
      temp_minute += to_string(minute);
  }
  return temp_hour + ":" + temp_minute;
}
string solution(int n, int t, int m, vector<string> timetable) {
  string answer = "";
  vector<int> timetable_int;
  vector<int> bus_timetable;
  int bus_arrive = 540;
  //timetable의 원소 int형태로 변환하기
  for(int i = 0 ; i<timetable.size() ; i++)
  {
      int temp = string_to_int(timetable[i]);
      if(temp > 1080 && temp < 1440) continue;
      timetable_int.push_back(temp);
  }
  //빠른 시간부터 봐야하기 때문에 정렬을 해준다.
  sort(timetable_int.begin(), timetable_int.end());
  //버스가 도착하는 시간을 vector에 저장해놓는다.
  for(int i = 0 ; i<n ; i++)
  {
      bus_timetable.push_back(bus_arrive + i*t);
  }
  //마지막 버스 이전까지 태울 수 있는 사람을 태우고 원소를 vector에서 제거하는 과정
  for(int i = 0 ; i<bus_timetable.size()-1 ; i++)
  {
      int count = 0;
      while(!timetable_int.empty() && count<m && timetable_int[0] <= bus_timetable[i])
      {
          timetable_int.erase(timetable_int.begin());
          count++;
      }
  }
  //마지막 버스에 대해 연산을 진행하는 과정
  int count = 0, result;
  while(!timetable_int.empty() && count<m && timetable_int[0] <= bus_timetable[n-1])
  {
      count++;
      if(count == m)
      {
          result = timetable_int[0] - 1;
          break;
      }
      timetable_int.erase(timetable_int.begin());
  }
  //만약 버스 자리에 여유가 있다면 버스가 도착한 시간이 가장 늦은 시간이 된다.
  if(count<m) result = bus_timetable[n-1];
  answer = int_to_string(result);
  return answer;
}