[프로그래머스(Programmers)][자바(java)] (Lv3) 셔틀버스

 

programmers.co.kr/learn/courses/30/lessons/17678

코딩테스트 연습 - [1차] 셔틀버스

 

문제 요약

• 콘은 역에서 셔틀버스를 타고 사무실까지 가야 함
  셔틀버스를 타기 위해서 역 앞의 대기열을 서야 함
  콘이 대기열에 도착할 수 있는 가장 늦은 시각을 구하는 문제 ( 셔틀을 탈 수 있는 시간 안에서 )
• 셔틀은 09:00 부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀이 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다.
  ( 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다. )
• 콘은 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다
• 모든 크루는 23:59에 집에 돌아가므로, 어떤 크루도 다음날 셔틀을 타는 일은 없다.
• 입력값으로 주어지는 String[] timetable은 각 크루들이 대기열에 도착한 시간을 의미 ( "hh:mm" 형식 )

 

문제 풀이

*  문자열 파싱, 해시, 정렬

-  모든 크루들의 대기열 도착 시간 배열( String[] timetable )을 오름차순으로 정렬

-  각 크루의 도착 시간( ct : crew_time )  timetable[i] 을 ":" 기준으로 파싱하여 시, 분으로 분류하고 시간을 분 단위로 변환

-  TreeMap 생성 ( TreeMap<Integer,List<Integer>> shuttle )
   -  key ☞ 셔틀버스의 도착 시간
   -  value ☞ 그 셔틀을 타는 크루들의 대기열 도착 시간

-  셔틀 도착 시간( st : shuttle_time )을 09:00부터 t분을 더해가며 구함 ( 분 단위로 변환 )  
   셔틀 도착 시간까지 대기열에 있던 크루들( ct <= st )을 최대 m명 까지 TreeMap에 넣음

-  셔틀의 마지막 도착시간( slt : shuttle_last_time )에 탑승한 크루들의 명 수( slm : shuttle_last_crew_num )를 구함
   -  slm이 m보다 작은 경우 ( 마지막 셔틀 도착시간에 탑승한 크루들의 인원 수가 최대 인원 수 보다 적을 때 )
      콘의 탑승 시간은 셔틀 도착 시간과 같다
  -  slm이 m보다 크거나 같은 경우
    콘의 탑승 시간은 가장 마지막에 탄 크루보다 1분 빠르다
    ( 가장 마지막에 탄 크루와 같으면 대기열에서 밀려나 셔틀을 탈 수 없게 됨 ) 

import java.util.*;

public class Solution {
	
	public String solution( int n, int t, int m, String[] timetable ) {
		int c = timetable.length, cc = 0, i;  // crew_num/cnt
		int st = 540, ct, mc;  // shuttle/crew_time_minute, member(crew on a bus)_cnt
		String cs[];  // crew_str
		TreeMap<Integer,List<Integer>> shuttle = new TreeMap<>();  // shuttle_treeMap
		Arrays.sort( timetable );
		for( i = 0; i < n; i++ ) {
			shuttle.put( st, new ArrayList<>() );
			mc = 0;
			while( cc < c && mc < m ) {
				cs = timetable[cc].split(":");
				ct = Integer.parseInt( cs[0] )*60 + Integer.parseInt( cs[1] );
				if( ct <= st ) {
					shuttle.get( st ).add( ct );
					mc++;
					cc++;
				}
				else
					break;
			}
			st += t;
			if( st >= 1440 )
				break;
		}
		List<Integer> slc;  // shuttle_last_crew
		int slt, slm;  // shuttle_last_time_minute, shuttle_last_crew_num
		slt = shuttle.lastKey();
		slc = shuttle.get( slt );
		slm = slc.size();
		if( slm < m )
			return String.format( "%02d", slt/60 ) + ":" + String.format( "%02d", slt%60 );
		else {
			int clt = slc.get( slm-1 ) - 1;  // crew_last_minute
			return String.format( "%02d", clt/60 ) + ":" + String.format( "%02d", clt%60 );
		}
	}
}