[Programmers] [1차] 셔틀버스
콘이 셔틀버스를 탈 수 있는 가장 늦은 시간을 구하는 문제이다.
문제해결 전략
우선 콘이 셔틀버스를 최대한 늦게 타기 위해서는 마지막 셔틀버스를 이용하면 된다.
만약 마지막 셔틀버스가 만석이라면 마지막에 탄 사람보다 1분만 먼저오면 무조건 버스를 탈 수 있게 된다.
마지막 셔틀버스가 만석이 아니라면 마지막 셔틀버스의 도착시간에 맞춰 버스를 타면 된다.
위의 세가지 경우를 모두 고려하면 쉽게 구할 수 있는 문제이다.
우선 줄을 선 크루들을 도착 시간 순으로 나열을 한 뒤, 가장 먼저 도착한 인원부터 버스에 태우고 시간을 더해준다. 이 과정을 막차 직전까지만 해 준다.
막차에 대해서는 태울 수 있는 인원-1 만큼만 태우고 나머지 한 자리에 대해서는 빈자리인지, 만석이라면 마지막에 탄 사람이 누구인지 확인하여 위의 조건을 적용해 주 면 된다.
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string solution(int n, int t, int m, vector<string> timetable) {
string answer = "";
vector<pair<int,int>> v;
for(int i=0;i<timetable.size();i++){
int H = (timetable[i][0] - '0')*10 + timetable[i][1] - '0';
int M = (timetable[i][3] - '0')*10 + timetable[i][4] - '0';
v.push_back(make_pair(H,M));
}
sort(v.begin(), v.end());
int cur = 9*60;
int idx = 0;
for(int i=0;i<n-1;i++){
for(int j=0;j<m;j++){
if(v[idx].first*60 + v[idx].second <= cur){
idx++;
}
}
cur += t;
}
for(int i=0;i<m-1;i++){
if(v[idx].first*60 + v[idx].second <= cur){
idx++;
if(idx == v.size())
break;
}
}
int temp = 0;
if(idx >= v.size()){
temp = cur;
}else if(v[idx].first*60 + v[idx].second <= cur){
temp = v[idx].first*60 + v[idx].second - 1;
}else{
temp = cur;
}
int hh = temp/60;
int mm = temp%60;
if(hh < 10)
answer += '0';
answer += to_string(temp/60) + ':';
if(mm < 10)
answer += '0';
answer += to_string(temp%60);
return answer;
}
출처 : 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/17678
211006 풀이
정렬 후 앞사람부터 버스 태우면서 만약 이번 버스가 마지막 버스라면 무조건 태워야 한다.
- 꽉찬 마지막 버스인 경우
마지막 사람보다 1분만 먼저오면 됨 - 여유있는 마지막 버스인 경우
버스 도착시간 맞춰 도착하면 됨 - 버스에 사람 다탔는데 자리 남은 경우
버스 도착시간 맞춰 도착하면 됨
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int change(string t){
int h1 = t[0] - '0';
int h2 = t[1] - '0';
int m1 = t[3] - '0';
int m2 = t[4] - '0';
return (h1*10+h2)*60 + m1*10 + m2;
}
string tostring(int t){
string h = to_string(t/60);
string m = to_string(t%60);
if(h.size() == 1)
h = '0' + h;
if(m.size() == 1)
m = '0' + m;
return h + ':' + m;
}
string solution(int n, int t, int m, vector<string> timetable) {
string answer = "";
sort(timetable.begin(), timetable.end());
int idx = 0;
int cur = 540;
int cnt = 0;
int bus = 0;
while(1){
if(idx >= timetable.size())
break;
int time = change(timetable[idx]);
if(time <= cur){
cnt++;
idx++;
if(cnt == m){
cur += t;
bus++;
cnt = 0;
if(bus == n){
answer = tostring(time-1);
return answer;
}
}
}else{
cnt = 0;
bus++;
if(bus == n){
answer = tostring(cur);
return answer;
}
cur += t;
}
}
return tostring(cur);
}
Author And Source
이 문제에 관하여([Programmers] [1차] 셔틀버스), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kms9887/Programmers-1차-셔틀버스저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)