[Programmers] 셔틀버스

단순 구현 문제이다.

단순 구현 문제이긴 하지만 조건들이 까다롭고 문제이해가 오래 걸려서 구현함에 있어 고생을 하였다. 이 문제를 품에 있어 시간을 60진수로 간주하고 int화 시켜서 문제를 접근하였다. 그리고 bus들을 map에 저장하여 남은 자리를들을 체크해주었고, 크루들을 한명씩 체크하며 버스의 마지막자리에 탈때의 시간, 그리고 남는 버스자리의 시간들을 비교하여 콘이 탈 시간의 최대값을 찾았다.

package programmers;
 
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Solution_2018카카오_셔틀버스 {
    public static void main(String[] args) {
//        int n=1; int t=2;int m=5;
//        String[] timetable= {"08:00", "08:01", "08:02", "08:03"};
        
        int n=2;int t=10;int m=2;
        String[] timetable= {"09:10","09:09","08:00"};
        
//        int n=2;int t=1;int m=2;
//        String[] timetable= {"09:00","09:00","09:00","09:00"};
 
//        int n=1;int t=1;int m=5;
//        String[] timetable= {"00:01","00:01","00:01","00:01","00:01"};
        
//        int n=1;int t=1;int m=1;
//        String[] timetable= {"23:59"};
        
//        int n=10;int t=60;int m=45;
//        String[] timetable= {"23:59","23:59","23:59","23:59","23:59","23:59","23:59",
//                "23:59","23:59","23:59","23:59","23:59"};
        
        System.out.println(solution(n, t, m, timetable));
    }
    
    static String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        
        int[] crews=new int[timetable.length];
        int index=0;
        for(String time :timetable) {
            crews[index++]=changeTimetoInt(time);
        }
        Arrays.sort(crews);
        
        Map<Integer, Integer> bus=new LinkedHashMap<>();
        
        int start=540; //09:00
       
        //버스 배정
        bus.put(start, m);
        for(int i=0;i<n-1;i++) {
            start+=t;
            bus.put(start, m);
        }
        
        int cornTime=0;        //콘이 탑승할시간
        
        Set<Integer> keys = bus.keySet();
        
        for(int crew:crews) {
            int gap=Integer.MAX_VALUE;                //시간차이
            int pick=0;                                //선택한 버스
            for(int key : keys) {
                if(crew<=key && bus.get(key)>0) {    //현재 crew가 탈수있는 버스이고, 버스에 자리가 있다면
                    if(key-crew < gap) {            //가장가까운 버스탑승
                        pick=key;
                        gap=key-crew;
                    }
                }
            }
            
            if(gap!=Integer.MAX_VALUE) {            //선택한 버스가 있다면
                bus.put(pick, bus.get(pick)-1);        
                
                if(bus.get(pick)==0 && crew-1 > cornTime) {        //만일 버스에 자리가 더이상 없다면
                    cornTime=crew-1;                //현재 crew보다 1분 먼저도착해야지 버스탑승가능        
                }
            }
        }
        
        for(int key : keys) {
            if(bus.get(key)>0  && key>cornTime)        //만일 버스에 자리가 있다면
                cornTime=key;
        }
        
        int hour=cornTime/60;
        if(hour<10) {
            answer+="0"+hour+":";
        }else
            answer+=hour+":";
        
        int minute=cornTime%60;
        if(minute<10) {
            answer+="0"+minute;
        }else
            answer+=minute+"";
        
        return answer;
    }
    
    static int changeTimetoInt(String time) {
        StringTokenizer st=new StringTokenizer(time,":");
        return Integer.parseInt(st.nextToken())*60 +Integer.parseInt(st.nextToken());
    }
}