문제
https://programmers.co.kr/learn/courses/30/lessons/17678?language=java
풀이
- 먼저 셔틀버스 시간표를 만들어준다. 09시부터 t분 간격으로 n회 배치하면 된다. t분씩 더해주다가 분(minute)단위가 60이 넘어가면 시(hour)를 1씩 올려주면 된다.
(bus[i][0]을 시, bus[i][1]을 분으로 두었다.)
bus = new int[n][2];
bus[0][0] = 9;
bus[0][1] = 0;
for (int i = 1; i < n; i++) {
bus[i][0] = bus[i - 1][0];
bus[i][1] = bus[i - 1][1] + t;
if (bus[i][1] >= 60) {
bus[i][0] += bus[i][1] / 60;
bus[i][1] = bus[i][1] % 60;
}
}- 추후 계산하기 쉽게 크루에 대한 입력 정보를 정수화하였다. 나중에 계산을 위해서 먼저 오름차순으로 정렬해주었다.
(문자열이든 숫자든 입력 값 형식이 일정하므로 다음과 같이 정렬하고 시작해도 문제 없다.)
Arrays.sort(timetable);
crew = new int[timetable.length][2];
for (int i = 0; i < timetable.length; i++) {
String[] inputs = timetable[i].split(":");
crew[i][0] = Integer.parseInt(inputs[0]);
crew[i][1] = Integer.parseInt(inputs[1]);
}- 크루를 셔틀버스에 탑승시킨다. 특정 셔틀버스 도착 시간보다 이르거나 같게, 해당하는 크루 중 선착순 m명을 탑승시켰다. 단, 마지막 버스와 최종적으로 남은 크루에 대해서는 별도의 계산이 필요하므로 남겨둔다.
int j = 0;
for (int i = 0; i < bus.length - 1; i++) {
int cnt = m;
int b1 = bus[i][0];
int b2 = bus[i][1];
while (cnt > 0 && j < crew.length) {
int c1 = crew[j][0];
int c2 = crew[j][1];
if (b1 * 60 + b2 >= c1 * 60 + c2) {
cnt--;
j++;
} else {
break;
}
}
}- 마지막 셔틀버스와 크루에 대해서 계산을 진행한다.
- 위의 과정을 거친 후 남은 크루가 마지막 셔틀 수용 가능 인원보다 많을 수 있다. 이 경우 콘은 마지막으로 탑승하는 인원보다 1분 빠르게 나와 대기해야 한다. (단, 09:00 -> 08:59 와 같은 경우에 대한 처리가 필요하다.)
- 이렇게 구한 시간이 마지막 셔틀 도착 시간보다 늦을 수 있다. 이 경우 마지막 셔틀 도착 시간으로 당겨야 한다.
int[] answer = new int[2];
answer[0] = crew[crew.length - 1][0];
answer[1] = crew[crew.length - 1][1];
if (crew.length - j < m) {
answer[0] = bus[bus.length - 1][0];
answer[1] = bus[bus.length - 1][1];
} else {
answer[0] = crew[j + m - 1][0];
answer[1] = crew[j + m - 1][1] - 1;
if (answer[1] == -1) {
answer[0]--;
answer[1] = 59;
}
}
if (bus[bus.length - 1][0] * 60 + bus[bus.length - 1][1] < answer[0] * 60 + answer[1]) {
answer[0] = bus[bus.length - 1][0];
answer[1] = bus[bus.length - 1][1];
}전체 코드
import java.util.*;
class Solution {
int[][] bus;
int[][] crew;
public String solution(int n, int t, int m, String[] timetable) {
// 셔틀 초기화
bus = new int[n][2];
bus[0][0] = 9;
bus[0][1] = 0;
for (int i = 1; i < n; i++) {
bus[i][0] = bus[i - 1][0];
bus[i][1] = bus[i - 1][1] + t;
if (bus[i][1] >= 60) {
bus[i][0] += bus[i][1] / 60;
bus[i][1] = bus[i][1] % 60;
}
}
// 크루 초기화
Arrays.sort(timetable);
crew = new int[timetable.length][2];
for (int i = 0; i < timetable.length; i++) {
String[] inputs = timetable[i].split(":");
crew[i][0] = Integer.parseInt(inputs[0]);
crew[i][1] = Integer.parseInt(inputs[1]);
}
int j = 0;
for (int i = 0; i < bus.length - 1; i++) {
int cnt = m;
int b1 = bus[i][0];
int b2 = bus[i][1];
while (cnt > 0 && j < crew.length) {
int c1 = crew[j][0];
int c2 = crew[j][1];
if (b1 * 60 + b2 >= c1 * 60 + c2) {
cnt--;
j++;
} else {
break;
}
}
}
int[] answer = new int[2];
answer[0] = crew[crew.length - 1][0];
answer[1] = crew[crew.length - 1][1];
if (crew.length - j < m) {
answer[0] = bus[bus.length - 1][0];
answer[1] = bus[bus.length - 1][1];
} else {
answer[0] = crew[j + m - 1][0];
answer[1] = crew[j + m - 1][1] - 1;
if (answer[1] == -1) {
answer[0]--;
answer[1] = 59;
}
}
if (bus[bus.length - 1][0] * 60 + bus[bus.length - 1][1] < answer[0] * 60 + answer[1]) {
answer[0] = bus[bus.length - 1][0];
answer[1] = bus[bus.length - 1][1];
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("%02d", answer[0]));
sb.append(":");
sb.append(String.format("%02d", answer[1]));
return sb.toString();
}
}처음에 생각보다 따져야 할 요소가 많은 것 같아 고민을 한참 했던 문제다. 어느 정도 규칙을 생각하고 적용하는 것이 중요한 것 같다.
Coding Duck