[c++] 2018 KAKAO BLIND RECRUITMENT[1차] 셔틀버스

문제

셔틀버스 문제 바로가기

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

 

풀이

1. 셔틀이 출발하는 시간을 다 구한다.
2. 사람들의 timetable을 오름차순으로 정렬한다.
3. 각 셔틀에 탈 수 있는 사람(셔틀 시간보다 작거나 같은 사람)을 구한다.
   1. 이 때, 콘이 해당 셔틀에 탈 수 있기 위한 최후의 시간을 구해놓는다.
   2. 최후의 시간은 셔틀에 사람이 꽉 찰 경우 '가장 큰 시간 - 1'
   3. 셔틀에 사람이 꽉 차지 않는다면 '셔틀 출발 시간'이다.
4. 각 셔틀에서의 최후 시간 중 가장 최후인 시간을 고른다.

 

코드

#include <string>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>

using namespace std;

int getTime(string timeString){
    auto idx = timeString.find(":");
    int hour = stoi(timeString.substr(0, idx));
    int minute = stoi(timeString.substr(idx+1, timeString.size()));
    
    return hour*60 + minute;
}

string getTimeString(int time){
    string hour = to_string(time / 60);
    string minute = to_string(time % 60);
    
    if(hour.size() == 1){
        hour = '0' + hour;
    }
    if(minute.size() == 1){
        minute = '0' + minute;
    }
    
    return hour + ":" + minute;
}

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    vector<int> shuttleTime;
    
    // 1. 셔틀이 출발하는 시간을 다 구한다.
    int nowTime = 9*60; // 첫 시간 세팅
    shuttleTime.push_back(nowTime);
    for(int i=0; i<n-1; i++){
        nowTime += t;
        shuttleTime.push_back(nowTime);
    }
    
    // 2. 사람들의 timetable을 오름차순으로 정렬한다.
    vector<int> numberTimeTable;
    for(int i=0; i<timetable.size(); i++){
        numberTimeTable.push_back(getTime(timetable[i]));
    }
    sort(numberTimeTable.begin(), numberTimeTable.end());
    
    // 3. 각 셔틀에 탈 수 있는 사람(셔틀 시간보다 작거나 같은 사람)을 구한다.
    // (이 때, 콘이 해당 셔틀에 탈 수 있기 위한 최후의 시간을 구해놓는다.)
    // => 이건 '가장 큰 시간 - 1분'이거나, 셔틀에 사람이 꽉 차지 않는다면 '셔틀 출발 시간'이다.
    vector<int> cornTime;
    int idx = 0;
    for(int i=0; i<shuttleTime.size(); i++){ // 10
        int shuttle = shuttleTime[i];
        int shuttleWhole = 0;
        int maxTime = 0;
        // *이미 버스에 탄 인원은 제외해주어야 함
        // *셔틀에 m명 이상 못 타게 해야 함
        for(; idx<numberTimeTable.size() && shuttleWhole != m; idx++){ // 2000
            if(numberTimeTable[idx] <= shuttle){
                shuttleWhole++;
                if(maxTime < numberTimeTable[idx]) maxTime = numberTimeTable[idx];
            }else{
                break;
            }
        }
        if(shuttleWhole < m){ // 셔틀 자리 남음
            cornTime.push_back(shuttle);
        }else{ // 자리 없으면 가장 큰 시간 - 1
            cornTime.push_back(maxTime-1);
        }
    }
    
    // 4. 각 셔틀에서의 최후 시간 중 가장 최후 시간을 고른다.
    sort(cornTime.begin(), cornTime.end());
    answer = getTimeString(cornTime.back());
    
    return answer;
}

 

결과

테스트 1 〉	통과 (0.02ms, 4.32MB)
테스트 2 〉	통과 (0.02ms, 4.25MB)
테스트 3 〉	통과 (0.02ms, 4.26MB)
테스트 4 〉	통과 (0.02ms, 3.78MB)
테스트 5 〉	통과 (0.02ms, 3.8MB)
테스트 6 〉	통과 (0.02ms, 4.21MB)
테스트 7 〉	통과 (0.08ms, 4.32MB)
테스트 8 〉	통과 (0.03ms, 4.26MB)
테스트 9 〉	통과 (0.02ms, 4.25MB)
테스트 10 〉	통과 (0.02ms, 4.27MB)
테스트 11 〉	통과 (0.02ms, 4.32MB)
테스트 12 〉	통과 (0.06ms, 4.32MB)
테스트 13 〉	통과 (0.06ms, 4.33MB)
테스트 14 〉	통과 (0.02ms, 4.26MB)
테스트 15 〉	통과 (0.03ms, 3.72MB)
테스트 16 〉	통과 (0.04ms, 4.32MB)
테스트 17 〉	통과 (0.06ms, 4.25MB)
테스트 18 〉	통과 (0.06ms, 4.27MB)
테스트 19 〉	통과 (0.06ms, 4.27MB)
테스트 20 〉	통과 (0.06ms, 4.33MB)
테스트 21 〉	통과 (0.20ms, 4.25MB)
테스트 22 〉	통과 (0.08ms, 3.92MB)
테스트 23 〉	통과 (0.06ms, 4.34MB)
테스트 24 〉	통과 (0.23ms, 3.9MB)

 

 부정확한 정보가 담겨있을 수 있습니다! 

 댓글로 알려주세요 :) 

도움이 되셨다면 광고 한 번씩 눌러주세요 ❣️