Algorithm

[CodeKata] 프로그래머스 : 6.5(토), 셔틀버스

ttaeng_99 2021. 6. 6. 17:50
반응형

🥋 Oooth More!! (Level 3)

* 해설링크 : https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

 

🧮 풀이

해당풀이로 풀었으나, 정답률이 87.5로 나왔다. (몇 가지 예외처리가 잘 안된듯)

function toMinute(time) {
  time = time.split(":");
  return time[0] * 60 + Number(time[1])
}

function toTime(m) {
  return String(Math.floor(m/60)).padStart(2,'0') + ":" + String(m%60).padStart(2,'0')
}

function solution(n, t, m, timetable) {
  let kornBus = 0;
  const busTable = Array.from({ length: n }, (_,i) => toMinute("09:00") + (i*t))
  timetable = timetable.map(time => toMinute(time)).sort((a,b) => b - a);

  for (let i = 0 ; i < busTable.length ; i++) {
    if (timetable[timetable.length-1] > busTable[busTable.length-1]) {
      kornBus = busTable[busTable.length-1]
      break;
    }
    const bus = busTable[i];
    const idx = timetable.findIndex((time) => time <= bus);
    const count = timetable.length - idx;

    if (count >= m) {
      kornBus = timetable[timetable.length-m] - 1;
      timetable.splice(timetable.length-m);
    }
    else {
      kornBus = bus;
      timetable.splice(idx);
    }
  }

  return toTime(kornBus)
}
  1. toMinute(), toTime() 은 각각 시간(String) -> 분(Number), 분(Number) -> 시간(String) 으로 변환해주는 함수다.
  2. kornBus는 콘이 탈 버스시간을 저장하기 위한 변수이다.
  3. 먼저, 버스가 운행되는 시간인 busTable, 크루들이 타는 시간을 분값으로 바꿔서 정렬(역순)한 timetable 두 배열을 준비했다.
  4. timetable을 역순으로 정렬한 이유는, findIndex()가 좌측부터 탐색하므로 현재 버스를 탈 수 있는 가장 큰 크루원의 시간값을 timetable에서 찾아야하기 때문에 큰 수부터 내림차순으로 정렬한 것이다.
  5. busTable을 순회하며 매 버스가 도착하는 상황을 고려한다. 우선, timetable 최소값이 busTable 최대값보다 크다면 남은 크루들이 마지막 버스보다 늦게오는 것이므로 가장 늦은 버스시간을 kornBus에 대입하고 break 한다.
  6. 이외에는, bus(현재 버스시간), idx(버스를 탈 수 있는 가장 늦는 크루원의 인덱스), count(버스를 타는 인원수) 를 산출한다.
  7. count가 m 이상이면 정원초과이다.(콘을 포함하므로) 이 땐, timetable 끝에서부터 m번째까지만 splice() 한다.
  8. kornBus 시간 역시 해당 버스를 타는 가장 늦은 크루원의 시간(timetable[timetable.length-m]) 보다 1분 일찍 와야한다.
  9. count가 m 미만이면 콘을 포함한 모든 크루가 버스를 탈 수 있다. 해당 버스시간을 kornBus에 저장하고 timetable은 탄 사람들 모두를 splice() 해준다. (idx 활용) 
  10. 모든 연산이 끝난, kornBus 값을 toTime() 함수를 통해 문자열로 반환해준다.

 

🖇 리뷰

function solution(n, t, m, timetable) {
    const getTime = time => time.substr(0, 2) * 60 + +time.substr(3);

    let answer = getTime('09:00'),
        last = (n - 1) * t + answer,
        crews = timetable.map(getTime).sort((a, b) => a - b).filter(v => v <= last);

    for (let i = 0; i < n; i++) {
        let crewsNum = crews.filter(crew => answer >= crew).length;

        if (i === n - 1) {
            if (crewsNum >= m) answer = crews[m - 1] - 1;
        } else {
            crews.splice(0, crewsNum > m ? m : crewsNum);

            answer += t;
        }
    }

    return String(Math.floor(answer / 60)).padStart(2, '0') + ':' + String(answer % 60).padStart(2, '0');
}

* 출처 : https://gwang920.github.io/algorithm/progreammers-2-17678/

  1. getTime() 함수는 내 toMinute() 함수처럼, 문자를 숫자(분)로 바꿔주는 함수이다. 이로, answer를 우선 첫 차인 9시로 설정한다.
  2. last는 마지막 버스시간, crews는 timetable을 getTime()을 통해 분값으로 바꾼 배열이다. 오름차순 정렬, last보다 늦는 값은 제외한다.
  3. crewsNum은 현재 버스를 탈 수 있는 인원수이다. 마지막(n-1)이고, crewsNum이 m 이상이 되어 정원초과인 경우, 마지막 인원보다 1분 빠른 값을 answer에 넣어준다.
  4. 아니라면, crews에서 버스를 탑승한 인원을 제거해준다. crewsNum이 m보다 작으면 이 값으로, 크다면 정원인 m으로 splice() .
  5. answer에 t(배차간격)을 더해가면서 이를 반복한다. 최종적으로 저장된 answer 값을 문자("00:00") 형태로 반환한다.

전체적인 모범답안들이 last(막차시간)을 구해서 여기에 해당되지 않는 크루를 필터링해줬다. 예외처리가 단순화된 것이다!

반응형