Today I Learned

오늘도 주말에 있을 코테 준비를 위해 카카오 기출이었던 코테 문제를 풀어보았다.

셔틀버스

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

문제

셔틀버스는 09:00부터 총 n회 t분 간격으로 역에 도착하며 하나의 셔틀에는 최대 m명이 탈 수 있다.
셔틀이 도착하면 도착한 순간에 대기열에 선 크루들을 대기 순서대로 태우고 바로 출발한다.
모든 크루는 23:59분에 집에 돌아간다.
크루가 대기열에 도착하는 시간을 String 배열 timetable로 줄 때, 셔틀을 타고 사무실로 갈 수 있는 가장 늦은 시각을 구하라.
0 ＜ n ≦ 10
0 ＜ t ≦ 60
0 ＜ m ≦ 45
timetable은 1~2000사이의 길이를 가지고 HH:MM의 형식으로 되어있다.

풀이 과정

기본적으로는 우선순위큐를 이용해 타임테이블의 시간을 다 넣고 가장 빠른 순부터 빼내면서 체크해나가면 되는 복잡하지 않은 로직이다.
하지만 시간을 비교가능하게 처리 후 연산이 끝난후 다시 String의 형태로 반환해야되는 점에서 까다롭다.

1. 우선 Integer 값을 담는 PQ를 하나 만들고 timetable의 시간들을 hour*60+min의 형태로 Integer 값으로 변환해 넣는다. substring(0,2)와 substring(3)을 사용하면 된다.

2. 첫 시간은 9*60이고 마지막 시간과 사람 수를 담을 변수가 필요하므로 선언과 초기화를 해둔다.

3. 반복문을 회차 기준 즉, n값을 기준으로 하나 만든다.

   매 반복마다 sum을 0으로 만들어주고 시작한다. sum은 m값 즉, 총 탈수 있는 사람 수를 체크하기 위한 변수이다. while문으로 pq의 값이 빌 때까지 반복문을 돌린다.
   peek()으로 pq에서 가장 빠른 시간을 불러와 first보다 그 값이 작거나 같으면서 정원을 초과하지 않는지 if문으로 체크해준다. 조건을 만족하면 poll()로 그 값을 꺼내주고 정원을 하나 늘린다.
   조건을 만족하지 않으면 break으로 while문을 깨고 다음 버스로 넘어가준다.

4. sum < m 이면 이전 차가 맞는거니 first-t로 돌려준다.

5. String.format을 이용해 hour와 min을 String값으로 바꿔주고 합쳐서 반환해준다.
   "%20d"를 사용해 :를 가운데 두고 합치면 HH:MM처럼 표시할 수 있다.

Java 코드

import java.util.*;

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        int first = 9 * 60;
        int last = 0;
        int sum = 0;
        
        for(String time : timetable) {
            int convertedTime = Integer.parseInt(time.substring(0,2)) * 60 + Integer.parseInt(time.substring(3));
            pq.add(convertedTime);
        }
        
        for(int i=0; i<n; i++){
            sum = 0;
            while(!pq.isEmpty()){
                int cur = pq.peek();
                if(cur<=first && sum < m){
                    pq.poll();
                    sum++;
                } else {
                    break;
                }
                last = cur - 1;
            }
            first += t;
        }
        
        if(sum < m) last = first - t;
        
        String hour = String.format("%02d", last/60);
        String min = String.format("%02d", last%60);
        String answer = hour + ":" + min;
        
        return answer;
    }
}