셔틀버스

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

처음에 문제 이해가 잘 되지 않았기 때문에 2가지 예시로 문제를 설명해 놓겠습니다.
출처: 프로그래머스

n:버스 개수 t:버스 간격(분) m:버스에 탈 수 있는 최대인원 timetable: 다른 크루의 버스정류장 도착시간

1번예제: 최대 인원은 5명인데 4명이 9시 전에 도착했다. -> 콘은 9시 정각에 도착해서 남은 1자리를 타면된다.
2번예제: 9시 정각에 8시에 도착한 크루만 탑승, 9시 10분이 되면 09:09분에 도착한 크루가 타고 남은 한자리는 콘이 타야된다. -> 콘은 09:09분에 도착해야된다.

이런식으로 예제를 이해하면 문제가 이해될 것 같습니다.
바로 문제 풀이로 들어가겠습니다.

해결방법

• 여기나오는 모든 시간을 분으로 바꾸고 답안제출시에만 시간으로 바꿔서 제출할 것입니다.

1. timetable을 분으로 바꾸고 오름차순으로 정렬한다. 23:59분에 기다리는 사람들은 어차피 집에 돌아가야되기 때문에 미리 배열에서 제거한다.
2. 변수 설정
   • start: 버스 시작시간
   • maxPeople: 버스가 운영할 동안 최대한 탑승가능한 인원
   • latTime: 마지막 버스운영 시간
   • tmp: 반복문을 돌면서 가장 마지막에 탄 사람을 저장해줄 변수이다.
3. n(버스개수)가 있을 때 까지 반복문을 돌아준다. 그리고 그 안에서 tmpM > 0 && timetable.length !== 0의 조건으로 다시 2중반복문을 돌아준다.
4. 2중 반복문을 돌면서 timetable[0] (먼저온사람)이 버스에 탈 수 있으면 태운다. (배열에서 제거하면서 maxPeople,tmpM을 -1 해준다.

while (tmpM > 0 && timetable.length !== 0) {
      if (timetable[0] <= start && maxPeople) {
        tmp = timetable.shift();
      }
      maxPeople--;
      tmpM--;
    }

5. 이렇게 2중 반복문을 마치면 tmp에 가장 마지막에 타는 사람이 들어와있다. 콘은 그사람보다 1분만 먼저오면 탈 수 있게된다. 하지만 예외사항이 있다.
   5-1. timetable이 비었있고 maxPeople이 남아있는 경우 (크루들이 버스를 이미 다 탔지만 아직 버스 좌석이 남아있는 경우이다.)
   5-2. tmp가 설정이 안 된 경우 (모든 크루가 버스 시간보다 늦게 도착해서 tmp가 설정이 안된 경우다.)

   => 두 경우에는 위에 변수에 저장했던 가장 마지막 버스가 출발하는 시간을 출력해주면된다.

code

function solution(n, t, m, timetable) {
  timetable = timetable
    .map((v) => parse(v))
    .filter((v) => v !== parse('23:59'));
  timetable.sort((a, b) => a - b);

  let start = 540;
  let maxPeople = n * m;
  const lastTime = 540 + t * (n - 1);

  let tmp = 0;
  while (n > 0) {
    let tmpM = m;
    while (tmpM > 0 && timetable.length !== 0) {
      if (timetable[0] <= start && maxPeople) {
        tmp = timetable.shift();
      }
      maxPeople--;
      tmpM--;
    }
    n--;
    start += t;
  }
  if ((timetable.length === 0 && maxPeople > 0) || !tmp)
    return toTime(lastTime);

  return toTime(tmp - 1);
}
//시간->분
function parse(time) {
  const [h, m] = time.split(':');
  return h * 60 + m * 1;
}
//분->시간
function toTime(minute) {
  let hour = Math.floor(minute / 60);
  hour = hour < 10 ? '0' + hour : hour;
  let minutes = minute % 60;
  minutes = minutes < 10 ? '0' + minutes : minutes;
  return `${hour}:${minutes}`;
}

마무리

문제 이해가 힘들었던 문제였다. 문제를 이해하고도 예상하지 못한 상황들이 있어서 코드를 몇 번이고 다시 구현했었다.
카카오에서 내준 예시인지 테스트예시가 예상치 못한 상황을 잘 보여주고 있었다. 덕분에 코드 수정이 편했다. 만약 주어지지 않는 경우도 있으니 테스트케이스를 평소에도 잘 연습해야 된다고 생각한다. 2중 반복문으로 코드 효율이 좋지 않았는데 효율성 테스트가 없어서 다행?이다.

요즘 알고리즘이 잘 풀리지 않고 좀 어렵다고 느껴진다. BFS를 공부하다가 접었었는데 BFS를 제대로 익히고 관련 문제를 찾아서 풀어보면서 집중력? 흥미? 를 다시 끌어올려야 될 것 같다.