문제 접근

문제에 대한 이해가 어렵지는 않으나, 구현하기 까다로운 유형이였다. 우선 시간을 순서대로 정렬하고, 버스시간과 비교해야한다. 또 시간을 HH:MM 형식의 스트링으로 변환도 해야하기에 굉장히 구현할게 많은 문제라고 느꼈다.

문제 풀이

import java.util.*;

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        ArrayList<Time> times = new ArrayList();
        StringTokenizer st;
        for(int i=0; i<timetable.length; i++) {
            st = new StringTokenizer(timetable[i], ":");
            times.add(new Time(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        Collections.sort(times, (t1, t2)->{
            if (t1.h == t2.h) return t1.m - t2.m;
            return t1.h-t2.h;
        });
        
        int lastInIndex = -1;
        int lastBusCount = 0;
        Time prevTime = new Time(8,60-t);
        Time curTime = null;
        for(int i=0; i<n; i++) {
            curTime = nextBusTime(prevTime, t);
            lastBusCount = 0;
            for(int j=lastInIndex + 1; j<times.size(); j++) {
                if (isIn(curTime, times.get(j))) {
                    lastBusCount++;
                    lastInIndex = j;
                    if (lastBusCount == m) break;
                } else {
                    break;
                }
            }
            prevTime = curTime;
        }
        
        // 버스에 탈 수 있는 사람이 없거나, 마지막 버스에 아직 빈자리가 있다면, 그냥 마지막 버스시간에 오면 됨.
        if (lastInIndex == -1 || lastBusCount < m) {
            return convertTo(curTime);
        }
        
        // 경쟁자들 뚫고 가장 늦은 시간 타기
        Time preFrontTime = times.get(lastInIndex);
        int i = lastInIndex - 1;
        for(; i>=0; i--) {
            Time frontTime = times.get(i);
            if (frontTime.h != preFrontTime.h || frontTime.m != preFrontTime.m) {
                return convertTo(frontOneMinute(preFrontTime));
            }
            preFrontTime = frontTime;
        }
        
        if (i==-1) return convertTo(frontOneMinute(preFrontTime));
        return answer;
    }
    
    Time nextBusTime(Time prevTime, int t) {
        int nextH = prevTime.h;
        int nextM = prevTime.m + t;
        if (nextM >= 60) {
            nextM-=60;
            nextH++;
        }
        return new Time(nextH, nextM);
    }
    
    boolean isIn(Time bus, Time person) {
        if (bus.h > person.h) return true;
        if (bus.h == person.h) return bus.m >= person.m;
        return false;
    }
    
    String convertTo(Time t) {
        StringBuilder sb = new StringBuilder();
        if (t.h < 10) {
            sb.append('0').append(t.h).append(':');
        } else {
            sb.append(t.h).append(':');
        }
        
        if (t.m < 10) {
            sb.append('0').append(t.m);
        } else {
            sb.append(t.m);
        }
        
        return sb.toString();    
    }
    
    Time frontOneMinute(Time t) {
        if (t.m == 0) return new Time(t.h-1, 59);
        return new Time(t.h, t.m-1);
    }
    
    
}

class Time {
    int h;
    int m;
    Time(int h, int m) {
        this.h = h;
        this.m = m;
    }
}