프로그래머스 - 2018 KAKAO BLIND RECRUITMENT [1차] 셔틀버스

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/17678

프로그래머스

처음 문제를 접했을 때.. 이게 뭐지 어떻게 풀어야 하지.. 라고 굉장히 막막한 기분이 들었다.

 

경우의 수가 너무 복잡해서 유용한 자료구조나 알고리즘이 잘 떠오르지 않았다.

 

그래서 일단 탐욕법으로 최대한 근접하게 답을 구할 수 있을 있는 방법을 시도하되,

 

경우의 수를 다 나눠서 처리하는 방법으로 했다.

 

 

 

//https://programmers.co.kr/learn/courses/30/lessons/17678
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#define BUSSTART 540

using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    vector<int> time(timetable.size());
    for(int i = 0; i < timetable.size(); i++) {
        string str = timetable[i];
        time[i] = stoi(str.substr(0,2)) * 60 + stoi(str.substr(3,2));
    }
    
    sort(time.begin(), time.end());
    
    int tIdx = 0;
    int ansTime = 0;
    int pNum = timetable.size(); // 승객 수
    bool lastBus = false;
    
    for(int bus = 0; bus < n; bus++) {
        int arvTime = BUSSTART +  bus * t;
        int busMax = m;
        while(true) {
            if(arvTime >= time[tIdx]) {
                if(bus == n - 1 && busMax == 1) {
                    ansTime = time[tIdx] - 1;
                    lastBus = true;
                    break;
                }
                tIdx++;
                busMax--;
            }
            else {
                break;
            }
            
            if(busMax == 0) break;
            if(tIdx == pNum) break;
            
        }
        
        if(lastBus) break;
        
    }
    
    
    
    if(!lastBus) {
        ansTime = BUSSTART + (n - 1) * t;
    }

    int hour = ansTime / 60;
    int minute = ansTime % 60;
    
    if(!(hour / 10)) {
        answer += '0';  
    }
     answer += to_string(hour) + ':';
    if(!(minute / 10)) {
        answer += '0';
    }
    answer += to_string(minute);
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~