코딩테스트 -- [1차] 셔틀버스 - (프로그래머스 / C++)

 

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

 

문제 설명

셔틀버스

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

---

요약하면 하루에 n번 t마다 오는 버스에 m명이 탈 수 있을 때 내가 가장 늦게 탈 수 있는 버스를 구하는 문제!

 

보자마자 생각나는 방법은 벡터로 구분짓기!

 

1. 사람들과 버스의 시간들을 각각 받는다

2. 버스 인덱스와 동일한 인덱스의 2차원 벡터를 만든다

3. 버스시간보다 빨리 도착한 사람 & 버스에 타있는(벡터에 추가된) 사람의 수가 m보다 적을 때 추가해준다.

 

4. 그리고 제일 마지막 위치 버스[n-1][m-1] 자리에 값이 있다면? 그 사람의 도착시간 -1,

없다면? 마지막 버스 시간에 맞춰서 오면 된다!

 

이렇게 만들어 주면 될 것 같습니다!

 

 

 

 

시작!

 

일단 함수 2개 먼저 추가해줍시다 지금 문제에서 "08:00"으로 값을 주기에 저는 int 형으로 변형해줍시다!

int change_int(string s){// 총 분으로
    int hour=0;
    int min=0;
    hour=stoi(s.substr(0,2))*60;
    min=stoi(s.substr(3,2));

    return hour+min;
}

하는 김에 모두 분으로 단위를 변경해줍시다

 

 

 

마찬가지로 int 형을 string 형으로 변경하는 함수도 하나 만들어줍시다.

string change_str(int s){// 분을 string으로
    string memo="";
    int hour=s/60;
    int min=s%60;
    
    if(hour<10){//시
        memo+="0"+to_string(hour)+":";
    }
    else{
        memo+=to_string(hour)+":";
    }
    
    if(min<10){//분
        memo+="0"+to_string(min);
    }
    else{
        memo+=to_string(min);
    }
    
    return memo;
}

 

 

 

이제 main함수 시작!

 

변수가 많나...?

    int startbus=540;//버스 시작
    int lastbus=540+(n-1)*t;//마지막 버스
    int time_ch=0;// 시간저장
    
    vector<int> member;//사람들 시간
    vector<int> bustime;// 버스시간들
    
    vector<vector<int>> bus_mem(n);버스에 사람들 저장할배열

 

 

사람들 시간을 받아줍시다

    for(string i : timetable){//사람들 받기
        time_ch=change_int(i);
        if(time_ch<=lastbus){
            member.push_back(time_ch);
        }   
    }
    
    if(member.size()==0){//다른사람들 다늦었을때
        return change_str(lastbus);
    }

여기서 만약 마지막 버스보다 늦게 오는 사람들이 있다면 걸러줍시다!

(이렇게 걸렀는데 아무도 없으면 모두 늦은 거니까 저는 마지막 버스시간에 맞춰서 가는 걸로 리턴!)

 

 

 

한번 걸러주고 정렬시켜줍시다.

    sort(member.begin(),member.end());//정렬
    
    for(int i=startbus;i<=lastbus;i+=t){//버스시간표 만들기
        bustime.push_back(i);
    }

그리고 마찬가지로 버스 시간표 만들기

 

 

 

그리고 핵심 부분인 버스에 사람 태우기! 

  for(int i: member){//버스채우기
        for(int j=0;j<n;j++){
            if(i<=bustime[j]){
                if(bus_mem[j].size()<m){
                    bus_mem[j].push_back(i);
                    break;
                }
            }
        }
    }

(정렬해놓았기에 앞에서부터 하나씩 가면서 맞는 버스에 태우면 됩니다!)

 

 

 

이제 마지막으로 마지막 배열 칸을 확인해줍시다!

    if(bus_mem[n-1].size()>=m){//마지막버스에 사람이 가득 있다면? 바로앞사람 시간-1
        return change_str(bus_mem[n-1][m-1]-1);
    }
    else{//없다면? 마지막 버스시간에 맞춰서
        return change_str(lastbus);
    }

 

 

 

 

좀 긴 거 같기도 하지만.. 성공!

 

 

 

 

 

*all

#include <string>
#include <vector>
#include <iostream>
#include<algorithm>
using namespace std;

int change_int(string s){// 총 분으로
    int hour=0;
    int min=0;
    hour=stoi(s.substr(0,2))*60;
    min=stoi(s.substr(3,2));

    return hour+min;
}

string change_str(int s){// 분을 string으로
    string memo="";
    int hour=s/60;
    int min=s%60;
    
    if(hour<10){//시
        memo+="0"+to_string(hour)+":";
    }
    else{
        memo+=to_string(hour)+":";
    }
    
    if(min<10){//분
        memo+="0"+to_string(min);
    }
    else{
        memo+=to_string(min);
    }
    
    return memo;
}


string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    int startbus=540;
    int lastbus=540+(n-1)*t;
    int time_ch=0;
    
    vector<int> member;
    vector<int> bustime;
    
    vector<vector<int>> bus_mem(n);
    
    int count=0;
    
    for(string i : timetable){//사람들 받기
        time_ch=change_int(i);
        if(time_ch<=lastbus){
            member.push_back(time_ch);
        }   
    }

    if(member.size()==0){//다른사람들 다늦었을때
        return change_str(lastbus);
    }
    
    sort(member.begin(),member.end());//정렬
    
    for(int i=startbus;i<=lastbus;i+=t){//버스시간표 만들기
        bustime.push_back(i);
    }
    
    
    for(int i: member){//버스채우기
        for(int j=0;j<n;j++){
            if(i<=bustime[j]){
                if(bus_mem[j].size()<m){
                    bus_mem[j].push_back(i);
                    break;
                }
            }
        }
    }
    
    
    if(bus_mem[n-1].size()>=m){//마지막버스에 사람이 가득 있다면? 바로앞사람 시간-1
        return change_str(bus_mem[n-1][m-1]-1);
    }
    else{//없다면? 마지막 버스시간에 맞춰서
        return change_str(lastbus);
    }
    
    
    return answer;
}

 

 

 

틀린 점이 있다면 댓 달아주세요!