[프로그래머스 Lv.2] 주차 요금 계산

[문제]

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

 

[풀이]

 

문제 지문이 길지만, 잘 읽어보는 것이 좋다고 생각한다. 지문 내에 배제해도 되는 조건들을 알려주기 때문에 코드 구현이 용이해지기 때문이다. 주요한 부분은 다음과 같다.

 

1. 같은 시각에 같은 차량의 입출입 내역은 2번 이상 존재하지 않음

2. 23:59에 입차되는 경우 없음

3. 주차장에 없는 차량의 출차 오류 없음

4. 이미 있는 차량이 다시 입차되는 오류 없음

5. fee의 0 ~ 3번 인덱스는 각각 기본시간, 기본요금, 단위시간, 단위요금만 들어옴

6. records의 각 요소는 무조건 "시간:분 차량번호 IN/OUT"으로만 들어옴

 

지문만 잘 읽고 파악하면 단순한 구현문제이기 때문에 쉽게 접근이 가능하다. 각 주차 데이터를 해시맵에 입력할 때, records의 모든 요소를 순회하면서 데이터를 정리하고, 각 데이터의 IN/OUT 여부를 판단하면서 일단 저장했다. 만약 도중에 OUT이 있으면 바로 시간을 산출할 수 있기 떄문에 map에 저장하고, 마지막으로 남은 요소들에 대해 다시 시간을 산출한다.

 

시간 산출용 데이터 저장 구조로 map을 사용한 이유는 오름차순 정렬로 answer를 return해야 되기 때문이다. min의 시간 산출이 끝난 후 각 데이터들에 대해 요금을 계산한다. 이후 이 값을 vector에 그냥 push_back해준 뒤 답을 return해주면 된다.

 

시간 복잡도는 O(nlogn)으로, 주어진 데이터에 대해 충분히 처리 가능하다.

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

using namespace std;

// 입차, 출차 기록을 보고, 차량 별 주차 요금 계산
// fees : 주차요금 기록
// records : 차량 입/출차 내역, 1이상 1,000이하, 시각 기준 오름차순 정렬 데이터
// records[i] : 시각, 차량번호, 입/출 내역
// 시각은 00:00~23:59, 번호는 4자리 숫자, 내역은 IN OUT만
// 출차 기록이 없으면 차량은 23:59 출차된 것으로 간주
// 같은 시각, 같은 차략 내역 2번 이상 없음, 23:59 입차 없음, 주차장에 없는 차량 출차 없음, 이미 있는 차량이 다시 입차되는 경우 없음
// 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return

int TimeCalculation(string _In, string _Out)
{
    // HH:MM 포맷에서 시간과 분을 추출
    int InHour = stoi(_In.substr(0, 2));
    int InMinute = stoi(_In.substr(3, 2));
    int OutHour = stoi(_Out.substr(0, 2));
    int OutMinute = stoi(_Out.substr(3, 2));

    // 전체 분으로 환산
    int InTotal = InHour * 60 + InMinute;
    int OutTotal = OutHour * 60 + OutMinute;

    // 차이 반환
    return OutTotal - InTotal;
}

int FeeCalculation(const vector<int>& fees, int TotalMin)
{
    int BaseTime = fees[0];
    int BaseFee = fees[1];
    int UnitTime = fees[2];
    int UnitFee = fees[3];
    int Result = 0;

    if (TotalMin <= BaseTime)
    {
        Result =  BaseFee;
    }
    else
    {
        int ExtraMin = TotalMin - BaseTime;
        int Units = (ExtraMin + UnitTime - 1) / UnitTime;
        Result = BaseFee + Units * UnitFee;
    }

    return Result;
}

vector<int> solution(vector<int> fees, vector<string> records) 
{
    vector<int> answer;
    unordered_map<string, string> ParkingMap;
    map<string, int> FeeMap;

    for (string Record : records)
    {
        string Time = Record.substr(0, 5); // first : 시각
        string Number = Record.substr(6, 4); // second : 차량번호
        string INOUT = Record.substr(11, Record.size()); // third : IN/OUT

        // IN이면 저장, OUT이면 계산
        if (INOUT == "IN")
        {
            ParkingMap[Number] = Time;
        }
        else if (INOUT == "OUT")
        {
            string INTime = ParkingMap[Number];
            int Min = TimeCalculation(INTime, Time);
            FeeMap[Number] += Min;
            ParkingMap.erase(Number);
        }
    }

    // 남은건 23:59로 처리
    for (unordered_map<string, string>::iterator StartIter = ParkingMap.begin(); StartIter != ParkingMap.end(); StartIter++)
    {
        string Number = StartIter->first; // 넘버
        string Time =  StartIter->second; // 시간
        int Min = TimeCalculation(Time, "23:59");
        FeeMap[Number] += Min;
    }

    // 각요금 계산
    for (map<string, int>::iterator StartIter = FeeMap.begin(); StartIter != FeeMap.end(); StartIter++)
    {
        string Number = StartIter->first;
        int Time = StartIter->second;
        int Fee = FeeCalculation(fees, Time);
        answer.push_back(Fee);
    }
    
    return answer;
}