[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/17678
[풀이]
계산하기 편하도록 도착시각을 모두 분으로 변환하여 우선순위 큐에 넣는다.
n번의 셔틀 운행에 대하여 크루가 셔틀 출발 시각 이전에 도착 및 버스 탑승 인원이 남아 탑승가능하다면 탑승시킨다.
이때 탑승한 크루가 마지막 탑승 크루일 수 있으므로 정답을 크루탑승시각-1 로 갱신해준다.
만약 마지막 버스에 자리가 남아있다면 그 버스의 출발시각이 가능한 가장 늦은 도착 시각이 된다.
[코드]
import java.util.*;
class Solution {
public String solution(int n, int t, int m, String[] timetable) {
String answer = "";
//콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(String time:timetable){
pq.add(convertToTime(time));
}
int departureTime = 9*60;
List<List<Integer>> bus = new ArrayList<>();
for(int i=0; i<n; i++)
bus.add(new ArrayList<>());
int ans = 0;
for(int i=0; i<n; i++){
while(!pq.isEmpty()){
int crew = pq.poll();
//버스 출발 시간보다 일찍 왔고, 버스 인원이 아직 다 차지 않았다면
if(bus.get(i).size() < m && crew<=departureTime){
bus.get(i).add(crew); //버스에 탈 수 있음
ans = crew - 1; //마지막 탑승자라면 그 탑승자보다 빨리 와야 사무실로 갈 수 있음
}
else{
pq.add(crew);
break;
}
}
departureTime += t;
}
//마지막 버스에 자리가 남으면 그 버스의 출발시각에 도차하면 됨
if(bus.get(n-1).size() < m){
ans = departureTime - t;
}
answer += converToString(ans);
return answer;
}
static int convertToTime(String s){
String[] arr = s.split(":");
int hour = Integer.parseInt(arr[0]);
int min = Integer.parseInt(arr[1]);
return hour*60+min;
}
static String converToString(int time){
String hour = String.format("%02d", time/60);
String min = String.format("%02d", time%60);
return hour+":"+min;
}
}
'알고리즘 공부 및 문제 풀이 > 프로그래머스(PRO)' 카테고리의 다른 글
[pro] 프로그래머스 level3 12927 야근 지수 (Java) - 우선순위 큐 (0) | 2023.01.26 |
---|---|
[pro] 프로그래머스 level3 17676 추석 트래픽 (Java) (0) | 2023.01.26 |
[pro] 프로그래머스 level3 42893 매칭 점수 (Java) - 문자열, 정규식 (0) | 2023.01.25 |
[pro] 프로그래머스 level3 60063 블록 이동하기 (Java) - BFS, 시뮬레이션 (0) | 2023.01.20 |
[pro] 프로그래머스 level3 42892 길 찾기 게임 (Java) - 이진트리 (0) | 2023.01.20 |