프로그래머스 Level 3 셔틀버스

셔틀버스 (프로그래머스 Level 3)

https://school.programmers.co.kr/learn/courses/30/lessons/17678

최근에 이진탐색으로 문제를 푸는 방식과 그 필요성에 대하여 다시금 생각할 수 있었다

• ‘최적화문제’를 ‘결정문제’로 만들 수 있다면, 그 문제는 이진탐색으로 풀 수 있다
  
• 최적화 문제 : 조건을 만족하는 특정한 값 ‘x’를 구하는 문제
  
• 결정 문제 : 특정한 값 x 가 조건을 만족하는지를 확인하는 문제
  (이전에 dp 문제를 이진탐색으로 판단하였으나,
  알고 보니 특정값 ‘x’뿐 아니라 다른 변수의 값을 고려할 필요가 있었다)
  
• 문제의 ‘상한’과 ‘하한’을 통해 ‘중간값’을 구할 수 있는지 확인하기
  

이번 문제인 경우
특정한 ‘시간’을 구하면 되는 문제이며
그 하한값과 상한값이 적은 편이기에 이진탐색으로 풀 수 있었다

Code

#include <string>
#include <vector>
#include <map>

using namespace std;

int getTimeValue(string str)
{
    int hour = (str[0] - '0') * 10 + (str[1] - '0');
    int minu = (str[3] - '0') * 10 + (str[4] - '0');

    return hour * 60 + minu;
}

const int startTime = getTimeValue("09:00");

string getTimetoValue(int timeValue)
{
    int hour = timeValue / 60;
    int min = timeValue - hour * 60;

    string strHour = to_string(hour);
    if (strHour.size() == 1)
        strHour = "0" + strHour;
    string strMin = to_string(min);
    if (strMin.size() == 1)
        strMin = "0" + strMin;

    string ret = strHour + ":" + strMin;
    return ret;
}

bool isRightTime(int n, int t, int m, map<int, int> times,const vector<int>& bus, int timeValue)
{
    int fullCount = n * m; // 버스에 타는 사람의 총 량

    for (int i = 0; i < n; i++)
    {
        int nowTime = bus[i];
        int nowCount = 0;

        // 나도 탈 수 있는 시간
        if (timeValue <= nowTime &&
            fullCount == 0)
        {
            // 이미 자리 꽉참
            return false;
        }

        for (auto& a : times)
        {
            // 탈 수 있는 시간이다
            if (nowTime >= a.first)
            {
                // 근데 내가 더 빨리 왔다
                if (timeValue < a.first &&
                    nowCount < m)
                {
                    return true;
                }

                if (nowCount + a.second > m)
                {
                    a.second -= (m - nowCount);
                    nowCount = m;
                    break;
                }
                else
                {
                    nowCount += a.second;
                    a.second = 0;
                    if (nowCount == m)
                        break;
                }
            }
            else
            {
                break;
            }
        }

        if (timeValue <= nowTime &&
            nowCount < m)
        {
            return true;
        }

        fullCount -= m;
    }

    return false;
}

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    map<int,int> times;
    vector<int> bus;

    int start = startTime;
    for (int i = 0; i < n; i++)
    {
        bus.push_back(start + t * i);
    }

    for (string str : timetable)
    {
        int timeValue = getTimeValue(str);
        times[timeValue]++;
    }

    int low = 0;
    int high = getTimeValue("23:59");

    while (low < high)
    {
        int mid = (low + high) / 2;
        if (mid == low)
            break;

        // 탈 수 있는 시간 중 가장 늦은값 구하기
        if (isRightTime(n, t, m, times,bus, mid))
        {
            low = mid;
        }
        else // 중간 값이 탈 수 없는 시간이니 아래로 낮춘다
        {
            high = mid;
        }
    }

    answer = getTimetoValue(low);
    return answer;
}