[프로그래머스] LV.3 셔틀버스 (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
• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
• 크루의 도착 시각 HH:MM은 00:01에서 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"

풀이

2018 카카오 블라인드 테스트에서 출제된 문제이다. 아니나 다를까 시간과 관련된 처리를 다루는 문제이다. 보통 시간과 관련되서는 신경써서 생각해야 할 부분이 있는데 관련 글은 해당 포스트를 참고해보면 좋을 듯 하다. 다행히 해당 문제는 시간 관련 이슈를 고민하지 않고도 풀 수 있는 문제이다.

시간처리 관련 함수

일단 시간을 처리하는 문제이므로 이 부분을 외부 함수로 구현하여 호출할 수 있도록 구현해주자. 해당 문제에서 요구하는 시간 처리는 다음과 같이 크게 3가지로 나누어 생각할 수 있다.

1. 현재 시간이 버스 시간 이전인지 체크하는 함수
   • 탑승인원 조건만 충족한다면 버스 시간 이하까지 대기하는 인원들은 모두 해당 버스를 이용 가능
2. 버스 시간 업데이트 함수
   • 현재 버스시간에 셔틀 운행 간격 등을 더한 시간값을 리턴
3. 위 시간 관련 처리를 마치고 결과값을 다시 리턴값 형태(HH:MM)로 변환하는 함수

1번의 경우는 두 개의 시간을 HH:MM 형태의 인자로 전달 받아 이를 분 단위로 환산한 후, 두 값을 비교하여 true 또는 false 값을 리턴하도록 설계할 수 있다.

const isBelowThanShuttleTime = (time1, time2) => {
  const [hour1, minute1] = time1.split(':');
  const [hour2, minute2] = time2.split(':');
  // 구조분해할당 된 각 값들은 문자열이므로
  // 계산을 위해 정수형과 곱셈을 통해 정수형으로 변환
  const times1 = hour1*60 + minute1*1;
  const times2 = hour2*60 + minute2*1;
  return times1-times2 >= 0 ? true : false;
}

2번의 경우는 HH:MM 형태로 시간값을 하나 전달 받고 셔틀 운행 간격을 나머지 인자로 전달받도록 구현하자. 이때 셔틀 운행 간격의 최대값은 60을 넘지 않기 때문에 별도로 시간값을 변환할 필요가 없다.

const updateShuttleTime = (time, period) => {
  const [hour, minute] = time.split(':');
  // 정수형 변환 (위와 동일)
  const times = hour*60 + minute*1;
  const next = times + period; // period는 정수
  // 다시 `HH:MM` 형태로 변환하여 리턴
  const format_to_timeStr(next);
}

3번은 분 단위로 변환된 정수값을 다시 HH:MM 형태로 변환하도록 만들어주자. 위에서 계산 과정의 역순으로 적용하면 된다. 다만 이때 10보다 작은 값들은 0을 추가해주도록 유의하자.

const format_to_timeStr = (times) => {
  const hour = (times/60) >> 0;
  const minute = times % 60;
  // 10보다 작은 경우를 체크하여 0 추가
  const hstr = hour > 9 ? hour : '0' + hour;
  const mstr = minute > 9 ? minute : '0' + minute;
  return hstr + ':' + minute;
}

timetable 정보 매핑

문제에서 주어진 timetable은 승객들의 탑승 시간이 정렬되지 않은 상태로 주어져 있다. 이 값을 오름차순으로 정렬한다면 버스가 도착했을 때 몇명의 승객이 탑승 가능한 지 쉽게 계산할 수 있을 것 이다. 따라서 먼저 timetable을 오름차순 정렬하도록 하자. 이때 위에서 만들어준 isBelowThanShuttleTime 함수를 사용해줄 수 있다. 의미는 약간 다르지만 어찌됐든 해당 함수는 두 개의 시간값을 받아 누가 더 큰 지 작은 지 비교한 값을 true 또는 false로 반환해주기 때문이다. 따라서 해당 값이 거짓이면 역순으로 정렬해주어 오름차순 정렬을 할 수 있다.

// a가 b보다 크면 정렬 => 오름차순
timetable.sort((a, b) => isBelowThanShuttleTime(b, a) ? 1 : -1);

정렬된 timetable을 통해 반복문을 돌면서 각 시간대의 몇명의 승객이 대기하고 있는지에 대한 정보를 매핑해주자. 매핑은 객체(Object)를 사용해도 되고 ES6의 Map을 사용해도 상관없다. 여기서는 Map을 사용해 매핑하고자 한다.

const map = new Map();

timetable.forEach(time => {
  // 매핑된 정보에 해당 시간대가 있다면 기존값 + 1
  if(map.has(time))
    map.set(time, map.get(time)+1);
  // 없을 경우 1명의 승객이 대기하고 있는 상황
  else
    map.set(time, 1);
});

도착 시각 중 제일 늦은 시각 구하기

위에서 매핑한 map의 정보를 가지고 제일 늦은 시각을 구해줄 수 있다. 일단 제일 늦은 시각이 되기 위해 가장 중요한 조건은 콘이 사무실에 도착할 수 있어야 한다는 점이다. 따라서 다음의 두 가지 경우를 생각할 수 있다.

1. 버스가 도착한 특정 시간대에 탑승 인원이 다 차지 않은 경우
2. 버스가 도착한 특정 시간대에 탑승 인원이 다 찬 경우

1번의 경우엔 콘이 해당 특정 시간대에 그대로 탑승할 수 있을 것이다. 그러나 2번의 경우에는 빈 자리가 없기 때문에 콘이 해당 시간대에 버스를 탑승할 수 없다. 그러나 콘은 어떻게든 사무실에 출근해야 하므로, 해당 시간대에 버스를 타거나 이보다 빠른 시간에 버스를 타야한다.

하지만 콘은 너무나 게으르기 때문에 이미 대기하고 있는 크루의 대기열에서 가장 마지막에 서게 된다. 즉 해당 시간대의 버스는 이용할 수 없다는 말과 같다. 따라서 게으른 콘이 가장 늦은 시간에 버스를 타기 위해서는 2번의 경우에서 특정 시간대보다 1분 빠른 시간대가 되어야 할 것 이다.

이때 셔틀 운행 횟수가 n이고 각 셔틀 당 탑승 인원 수가 m이기 때문에 두 개의 값으로 이중 반복문을 돌면서 제일늦은 시간을 탐색하도록 하자.

let answer = '';	// 정답 시간대를 담을 변수
let shuttle = '09:00';	// 초기 셔틀 출발 시간

...

for(let i = 0; i < n; i++) {
  // 각 셔틀 당 탑승인원
  const pendinglist = [];
  // 매핑된 정보에 접근하여 key(시간)값에 접근
  for(const [key, value] of map) {
    // 현재 셔틀 시간과 실제 승객들의 대기시간을 비교
    if(isBelowThanShuttleTime(key, shuttle)) {
      for(let j = 0; j < m; j++) {
        // 해당 시간대 대기열의 승객이 0명이 되는 경우
        if(!map.get(key)) {
          // 해당 시간대 정보를 지우고 반복문 종료
          map.delete(key);
          break;
        }
        
        // 현재 셔틀 탑승인원이 다 찬 경우 반복 종료
        if(pendinglist.length === m) break;
        
        // 그 외 현재 셔틀 탑승인원을 하나 늘리고
        pendinglist.push(key);
        // 매핑 정보에서 해당 시간대의 대기 승객 수를 하나 줄인다.
        map.set(key, map.get(key)-1);
      }
      
      // 바로 위에서 대기 승객 수를 1 줄이고 값이 0이 되었을 때
      // 해당 값을 제거해야 하는데 반복문이 끝나 제거하지 못 할 수 있으므로
      // 최종적으로 이를 체크하여 제거
      if(!map.get(key)) map.delete(key);
    } else break;	// 현재 셔틀 버스 시간보다 느리면 종료
    
    // 위에서 언급한 두 조건
    // 현재 탑승인원이 버스 수송가능 인원보다 작다면
    if(pendinglist.length < m)
      // 콘은 현재 셔틀 시간에 탑승 가능
      answer = shuttle;
    // 현태 탑승인원이 버스 수송가능 인원과 같다면
    else if(pendinglist.length === m)
      // 콘은 사무실에 도착하기 위해
      // 현재 탑승 인원 중에 가장 마지막에 탑승한 인원보다
      // 1분 빠르게 도착한 시간대가 되어야 함
      answer = updateShuttleTime(pendinglist[pendinglist.length-1], -1);
    
    // 모든 버스 운행이 끝나기 전까지
    // 버스 도착 후 다음 버스의 도착 시간을 업데이트
 	// 따라서 각 시간대별로 가장 느린 시각을 계산 가능
    shuttle = updateShuttleTime(shuttle, t);
  }
  
  return answer;

전체코드

주어진 타임테이블을 잘 매핑하여 승객수를 잘 체크하여 문제 조건에 맞게 가장 느린 시간대를 구한다면 쉽게 풀이가 가능할 것을 생각한다. 주석을 제외한 전체 코드는 다음과 같다.

function solution (n, t, m, timetable) {
  let answer = '';
  let shuttle = '09:00';
  const map = new Map();
  
  timetable.sort((a, b) => isBelowThanShuttleTime(b, a) ? 1 : -1);
  timetable.forEach(time => {
    if(map.has(time))
      map.set(time, map.get(time)+1);
    else
      map.set(time, 1);
  });
  
  for(let i = 0; i < n; i++) {
    const pendinglist = [];
    for(const [key, value] of map) {
      if(isBelowThanShuttleTime(key, shuttle)) {
        for(let j = 0; j < m; j++) {
          if(!map.get(key)) {
            map.delete(key);
            break;
          }
          
          if(pendinglist.length === m) break;
          
          pendinglist.push(key);
          map.set(key, map.get(key)-1);
        }
        
        if(!map.get(key)) map.delete(key);
      } else
        break;
    }
    
    if(pendinglist.length < m) 
      answer = shuttle;
    else if(pendinglist.length === m)
      answer = updateShuttleTime(pendinglist[pendinglist.length-1], -1);
    
    shuttle = updateShuttleTime(shuttle, t);
  }
  
  return answer;
}

const isBelowThanShuttleTime = (time1, time2) => {
  const [hour1, minute1] = time1.split(':');
  const [hour2, minute2] = time2.split(':');
  const times1 = hour1*60 + minute1*1;
  const times2 = hour2*60 + minute2*1;
  return times2-times1 >= 0 ? true : false;
}

const updateShuttleTime = (time, period) => {
  const [hour, minute] = time.split(':');
  const times = hour*60 + minute*1;
  const next = times + period;
  return format_to_timeStr(next);
}

const format_to_timeStr = (time) => {
  const hour = time / 60 >> 0;
  const minute = time % 60;
  const hstr = hour > 9 ? hour : '0' + hour;
  const mstr = minute > 9 ? minute : '0' + minute;
  return hstr + ':' + mstr;
}

출처

https://programmers.co.kr/learn/courses/30/lessons/17678