[프로그래머스]2018카카오블라인드:[1차] 셔틀버스(java)

문제보러가기

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

이문제는 당시에 난이도 상에 포함되었던 문제라고 한다. 막상 풀이를 보게 되면 별거 없는 거 같지만, 어떻게 구현해서 풀어야겠다는 감이 잘 오지 않을 수 있다! 나의 경우는 문제 이해부터가 오래 걸렸던 거 같다 ㅎ..

 

 

 

 

문제풀이

- 크루들의 도착시간인 timetable을 int로 변환하여 오름차순으로 정렬하기 위해 PriorityQueue에 저장한다.

- 첫차 출발시간인 09:00시부터 t분 간격으로 n 대까지 탐색하며,

   큐에 담겨있는 크루의 도착시간 중 해당 셔틀 시간에 탈 수 있는지를 검사하여 list에 담아준다.

- 만약 해당 셔틀을 탈 수 없다면 큐에서 제거한 크루를 다시 넣어준다.

- 현재 크루보다 항상 1분씩 빨리 와야 탈 수 있기 때문에 answer를 갱신해주면서 진행한다.

  이렇게 갱신하다 보면 마지막으로 셔틀에 탑승하는 크루보다 1분 일찍 오는 시간이 answer이 된다.

- 가장 늦게 셔틀버스를 타는 경우를 구해야 하므로 만약 마지막 셔틀이 비어있다면 그 시간이 answer이 된다.

 

 

 

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
       	int answer = 0;
        //크루들 도착시간 오름차순 정렬하여 빼서 쓰기위해
		PriorityQueue<Integer> q = new PriorityQueue<>();
        //셔틀버스 시작시간인 09:00시
		int departT = 9*60;
		List<Integer>[] list = new List[n];
        
        //크루들 도착시간을 숫자로 변환하여 큐에 저장
		for (int i = 0; i < timetable.length; i++) {
			int hh = Integer.parseInt(timetable[i].split(":")[0]);
			int mm = Integer.parseInt(timetable[i].split(":")[1]);
			int time = hh*60 + mm;
			
			q.add(time);
			
		}
		
        //09:00시부터 시작하여 시간간격 t만큼 셔틀버스 배치
        //총 몇대 운행하는지로 반복문 사용
		for (int i = 0; i < n; i++) {
			list[i] = new ArrayList<>();
            
            //기다리고 있는 크루들이 있을경우
			while(!q.isEmpty()) {
				int arrivedT = q.poll();
                //현재 도착해있는 셔틀버스보다 일찍 도착하고, 셔틀버스 정원이 차지 않았을 경우
				if(arrivedT <= departT && list[i].size() < m) {
                	//셔틀버스에 크루를 태움 -> 셔틀버스 정원 확인하기 위해
					list[i].add(arrivedT);
				}
                //현재 도착해있는 크루가 없을 경우 이미 뺀 크루의 시간을 다시 넣어줌
				else {
					q.add(arrivedT);
					break;
				}
                //마지막 크루보다 1분 일찍 와야되므로 계속 갱신해줌
				answer = arrivedT-1;
			}
            //다음 셔틀버스 도착시간 갱신
			departT += t;
			

		}
        //마지막 버스가 비었을 경우 마지막 버스 도착시간에 맞춰서 오는게 정답
		if(list[n-1].size() < m) {
			answer = departT - t;
		}
		String hh = String.format("%02d",answer/60);
		String mm = String.format("%02d",answer%60);
        return hh+":"+mm;
    }
}