셔틀버스

programmers.co.kr/learn/courses/30/lessons/17678

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

<java>

class Solution {
    
    
    public String changeStr(int ianswer){
        int hour = ianswer/60;
        int minute = ianswer%60;
        String shour="";
        String sminute="";
        if(hour<10){
            shour = "0"+ Integer.toString(hour);
        }
        else{
            shour = Integer.toString(hour);
        }
        
        if(minute<10){
            sminute = "0"+Integer.toString(minute);
        }
        else{
            sminute = Integer.toString(minute);
        }
        
        String sanswer = shour+":"+sminute;
        return sanswer;
    }
    
    
    public String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        int ianswer =0;
        int[] timecnt = new int [1441];
        for(int i=0; i<timetable.length; i++){
            String time = timetable[i];
            int total = Integer.parseInt(time.substring(0,2))*60+Integer.parseInt(time.substring(3,5));
            timecnt[total]++;
        }

        int bustime = 9*60+(n-1)*t; // 마지막 버스시간
        int people =0; 
   
        int start =0;
        int end = 9*60;

        for(int i=0; i<n; i++){ // 버스가 올 때마다 

            for(int j = start; j<=end; j++){ //start부터 end시간까지 몇명의 크루들이 줄서는지기록
                
                people += timecnt[j];
                
            }
            
            if(i==n-1){ //마지막 버스일때 
                int tmp = end; 
                while(people>=m){ //남아있는 사람이 m명 이상이 아닐때의 시간을 구한다
                    people-=timecnt[tmp];
                    tmp--;
                }
                ianswer = tmp;
            }
            else{
                
                people = Math.max(people-m, 0); //버스를 타고 남아있는 사람들의 수
                start = end+1;// 버스 지나가고 1분 뒤
                end = end+t; // 그다음 버스가 올 시간
                
            }
          }
        
        

         answer =changeStr(ianswer);
        return answer;
    }
}

- 특정 버스시간에 몇명이 줄서있는지 1차원 배열에 기록 

- 버스가 올때마다 남아있는 사람들이 몇명인지 people 변수에 저장 

- 마지막 버스 차례일때, 남아있는 사람이 m 보다 작은 시점이 언제인지 찾아낸다. 

<c++>

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

int changetime(string str){ //string형 시간을 int 형으로
    stringstream ss(str);
        int t[2];
        string tmp;
       int  j=0;
        while(getline(ss,tmp,':')){
            t[j]= stoi(tmp);
            j++;
        }
    return 60*t[0]+t[1];
}

string inttostr(int time){ // int형 시간을 string으로
    string hour,minute;
    hour = to_string(time/60);
    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>times;
    vector<int>came;
    
    for(int i=0; i<timetable.size(); i++){ 
   		times.push_back(changetime(timetable[i]));  //크루들이 오는시간들을 int로 만든다.
    }
    sort(times.begin(),times.end()); //그리고 정렬을 한다
    int bustime = 9*60; // 버스의 첫 타임은 9시
    
    for(int i =0; i<n; i++){ //버스가 오는 횟수만큼 시간간격 t을 더하면서 came 벡터에 저장
        came.push_back( bustime); 
        bustime+=t; 
    }
    int targetbus = came[came.size()-1]; // 타겟버스는 가장 마지막 버스
    
    if(times[0]>targetbus){answer = inttostr(targetbus); return answer;}
    //만약 가장 먼저나오는 크루의 시간이 마지막 버스보다 더 늦게 나오는 시간이라면 적어도 마지막 버스시간이 답이 되어야함
    
    int cs = 0 ; //첫번째 크루
 
    int count =0;
    int i;

    for( i=0; i<came.size(); i++){ //버스 탐색
        count =0;
        while(times[cs]<=came[i] && count<m && cs <times.size()){
      //크루도착시간<= 버스도착시간 , 버스인원을 넘지 않고, 크루 인원을 넘지 않을때
            cs++; // 크루탐색 인덱스를 증가
            count++; // 하나의 버스에 타고있는 크루의 수 증가
           
         }
        if(cs==times.size()){break;}
     }

    if(i<came.size()-1){ // 모든 크루가 타고도 버스가남는다면
        answer = inttostr(targetbus); // 마지막 버스를 타면됨
    }
    else {
        if(count==m){ 마지막 버스인데모든 크루가 다 타지 못하거나 꽉찼다면
        cs--; //while문을 아까 돌면서 ++ 한것을 -- 해줌(마지막으로 탐색한 인덱스를 돌려놓음)
        answer = inttostr(times[cs]-1); //마지막으로 타는 애보다 1분 더빨리온다.
        }
        else{answer = inttostr(targetbus);} // 크루가 타고서도 남으면 마지막 버스타기
    }

    return answer;
}

- 그리디 문제인것 같다 

- 버스시간과 크루 도착시간 배열을 정렬하고 버스를 탐색하면서 크루가 해당 버스를 탈수 있으면 크루를 가르키는 인덱스를 증가시키면서 하나의 버스에 버스 수용가능인원을 채우도록한다.