[프로그래머스][C++] 주차 요금 계산

주차 요금 계산

문제 링크

주차 요금 계산

분석

주차 요금을 계산하는 문제입니다.

차량별 누적 주차 시간을 계산해야합니다.
기본 시간을 초과한 경우 단위 시간 단위로 추가 요금을 계산합니다.
출차 기록이 없는 경우 23:59 출차로 처리합니다.

풀이

#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>

using namespace std;

// records의 시간을 분으로 변환
int timeToMinutes(const string& time)
{
    // 시
    int hours = stoi(time.substr(0, 2));
    // 분
    int minutes = stoi(time.substr(3, 2));
    
    return hours * 60 + minutes;
}

vector<int> solution(vector<int> fees, vector<string> records) {
    vector<int> answer;
    
    // 주차된 총 시간
    map<string, int> parkingTime;
    // 입차 시간
    map<string, int> inTime;
    
    // 입/출차 순회
    for (const auto& record : records)
    {
        // 문자열을 분리하기위해 사용
        stringstream ss(record);

        // 분리한 문자열 저장할 변수
        string time;
        string carNumber;
        string info;

        // 시간, 차량 번호, 입/출차 기록으로 분리
        ss >> time >> carNumber >> info;
        
        // 시간을 분으로 변환
        int minutes = timeToMinutes(time);
        
        if (info == "IN")
        {
            // 입차인 경우 입차 시간을 분으로 저장
            inTime[carNumber] = minutes;
        }
        else
        {
            // 출차인 경우 출차 시간 - 입차 시간으로 주차된 시간을 구하고 저장
            parkingTime[carNumber] += minutes - inTime[carNumber];
            inTime.erase(carNumber);
        }
    }
    
    // 입차 기록만 있고 출차 기록이 없는 차량 처리
    for (const auto& e : inTime)
    {
        // 출차 시간 - 입차 시간으로 주차된 시간을 구하고 저장
        parkingTime[e.first] += timeToMinutes("23:59") - e.second;
    }
    
    // 각 차량별로 주차된 시간을 순회해서 요금으로 변환
    for (const auto& e : parkingTime)
    {        
        int fee = 0;
        if (e.second <= fees[0])
        {
            // 주차한 시간이 기본 시간보다 적은 경우 기본 요금
            fee = fees[1];
        }
        else
        {
            // 주차한 시간이 기본 시간보다 많은 경우
            // 기본 시간에 대한 요금과 단위 시간에 대한 요금을 계산
            fee = fees[1] + ceil((double)(e.second - fees[0]) / fees[2]) * fees[3];
        }
        
        answer.push_back(fee);
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• records를 순회하는 반복문 $O(n)$
• inTime를 순회하는 반복문 $O(m)$
• parkingTime를 순회하는 반복문 $O(m)$
• $O(n + m + m)$

공간 복잡도는 $O(m)$입니다.

• 주차된 총 시간을 저장하는 parkingTime $O(m)$
• 주차 중인 차량들의 입차 시간을 저장하는 inTime $O(m)$
• 반환될 값을 저장하는 answer $O(m)$
• $O(m)$

테스트 1 〉 통과 (0.03ms, 4.16MB)
테스트 2 〉 통과 (0.03ms, 4.21MB)
테스트 3 〉 통과 (0.04ms, 4.2MB)
테스트 4 〉 통과 (0.11ms, 4.21MB)
테스트 5 〉 통과 (0.15ms, 4.21MB)
테스트 6 〉 통과 (0.15ms, 4.2MB)
테스트 7 〉 통과 (1.24ms, 3.91MB)
테스트 8 〉 통과 (0.72ms, 4.2MB)
테스트 9 〉 통과 (0.23ms, 4.21MB)
테스트 10 〉 통과 (1.05ms, 4.21MB)
테스트 11 〉 통과 (1.88ms, 4.21MB)
테스트 12 〉 통과 (1.42ms, 3.95MB)
테스트 13 〉 통과 (0.05ms, 3.64MB)
테스트 14 〉 통과 (0.03ms, 4.21MB)
테스트 15 〉 통과 (0.02ms, 4.14MB)
테스트 16 〉 통과 (0.03ms, 4.21MB)