문제
영식이는 민식이와 함게 고속버스를 타고 캠프를 가야 하지만, 민식이는 영식이를 깨우지 않고 혼자 버스를 타고 캠프에 가버렸다.
영식이는 혼자 고속버스터미널까지 가서 캠프에 오려고 한다. 터미널에는 캠프 장소까지 운행하는 N가지의 버스가 있다. 각각의 버스는 시작 시각, 간격, 대수의 정보를 가지고 있다. 예를 들어, 어떤 버스의 시작 시각이 특점 시점을 기준으로 10분 후이고, 간격은 10분이고, 대수가 5대이면, 이 버스는 10분, 20분, 30분, 40분, 50분에 한 대씩 출발한다.
영식이는 버스터미널에 T분에 도착했다. 영식이가 버스를 타려면 최소 몇 분을 더 기다려야 하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 버스의 개수 N과 영식이가 버스터미널에 도착하는 시간 T가 주어진다. 둘째 줄부터 총 N개의 줄에 각 버스의 시작 시각 Si, 간격 Ii, 대수 Ci가 공백을 사이에 두고 주어진다.
출력
첫째 줄에 영식이가 기다려야 하는 시간을 출력한다. 영식이가 도착하는 동시에 버스가 출발하면 정답은 0이다. 만약 버스가 없어서 캠프에 갈 수 없으면 -1을 출력한다. 정답은 231보다 작다.
예제 입력 1
1 285
150 50 10예제 출력 1
15예제 입력 1
1 285
150 50 10예제 출력 1
15풀이 및 해설
출력값: 영식이가 버스를 타기까지 기다려야하는 최소 시간(만약, 탈 버스가 없으면 -1 출력)
1. 시작시간을 기준으로 오름차순 정렬
2. 가장 앞에 있는 버스 출발 시간이 영식이가 터미널에 도착한 시간 비교
2-1. 버스 출발 시간 >= 영식이가 터미널에 도착한 시간: 기다려야 하는 시간 출력
2-2. 버스 출발 시간 < 영식이가 터미널에 도착한 시간: 버스의 대수가 남아있는 상태인 경우에만 버스의 출발 시간 + 간격 더해서 배열에 다시 넣은 후, 버스 출발 시간 기준 오름차순 정렬
Code
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [N, T] = input[0].split(' ').map(Number); // N: 버스의 개수, T: 영식이가 버스터미널에 도착하는 시간
const busInfo = [];
for (let i = 1; i <= N; i++) busInfo.push(input[i].split(' ').map(Number)); // 버스별 시작 시간, 간격, 대수
busInfo.sort((a, b) => b[0] - a[0]); // 버스 출발 시간(=처음은 시작시간) 기준으로 내림차순 정렬
while (busInfo.length > 0) {
let [start, term, count] = busInfo.pop(); // 가장 출발 시간이 빠른 버스 꺼내기
if (start >= T) return console.log(start - T); // 가장 빨리 탈 수 있는 버스의 출발시간까지 기다려야 하는 시간
// 남아있는 대수가 있는 경우 해당 버스의 다음 출발 시간 저장
if (count > 1) {
busInfo.push([start + term, term, count - 1]);
busInfo.sort((a, b) => b[0] - a[0]);
}
}
console.log(-1); // 버스를 탈 수 없는 경우코드 개선하기
- 위에서 작성한 코드는 정렬을 계속 해주어야 하기 때문에 비효율적임!
각 버스 당 T 이후 처음 탈 수 있는 시각 찾아서 최솟값 구하기
- N개의 버스 별 가장 빨리 탈 수 있는 시간 구하기
- 영식이가 버스 터미널에 도착한 시간 <= 해당 버스의 출발 시간 → S - T 구해서 최솟값에 갱신 후 다른 버스 확인
- 영식이가 버스 터미널에 도착한 시간 > 해당 버스의 출발 시간
→ cnt(보내야 하는 버스 수) = ceil((터미널에 도착한 시간 T - 버스 출발 시간 S) / term)
- cnt >= C 인 경우는 해당 버스는 탈 수 없으므로 다른 버스 확인
Code
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [N, T] = input[0].split(' ').map(Number); // N: 버스의 개수, T: 영식이가 버스터미널에 도착하는 시간
let answer = Number.MAX_SAFE_INTEGER;
for (let i = 1; i <= N; i++) {
const [S, I, C] = input[i].split(' ').map(Number); // 버스별 시작 시간, 간격, 대수
// 영식이가 버스 터미널에 먼저 도착한 경우 시작 버스 탑승 가능
if (T <= S) answer = Math.min(answer, S - T);
else {
const count = Math.ceil((T - S) / I); // 이미 출발한 버스 수
if (count >= C) continue; // 해당 버스는 탈 수 없음
const waitTime = count * I + S - T; // 영식이가 탈 버스를 기다려야 하는 시간
answer = Math.min(answer, waitTime);
}
}
console.log(answer === Number.MAX_SAFE_INTEGER ? -1 : answer); // 아무것도 탈 수 없는 경우 -1 출력