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

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

프로그래머스

 

2022 KAKAO BLIND RECRUITMENT에 나온 문제이다.

주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 한다.

 

조건

• 차량이 입차되면 IN, 출차되면 OUT 기록이 주어진다.
• 출차 기록이 없는 차량은 23:59에 출차한 것으로 간주한다.
• 차량 번호가 같은 차량이 여러 번 입차할 수 있으며, 이를 누적 계산해야 한다.
• 같은 차량 번호는 오름차순으로 정렬하여 결과를 출력해야 한다.

풀이 방법

생각보다 여러 함수를 조합해야 해서 헷갈렸다.

더 간단히 푸는 방법도 있겠지만 내가 생각한 방법은 이렇다.

 

먼저, hashmap을 사용한다. 차량을 계속 검색해야 하므로 O(1)의 시간복잡도가 걸리는 hashmap을 선택했다.

입차 기록은 차량 번호를 키로, 입차 시간을 값으로 저장한다.

 

stringstream을 사용하여 문자열을 시간, 차량 번호, 상태(IN/OUT)로 파싱한다.

시간을 substr로 잘라서 분단위로 변환한다. 이렇게 하면 시간 계산이 훨씬 편리해진다.

 

unordered_map은 순서가 없으므로, 데이터를 vector<pair>로 변환한 뒤, 차량 번호를 기준으로 오름차순 정렬한다.

이후 요금 표를 사용하여 요금을 계산한다.

 

이때 중요한 점은 같은 번호의 차량이 여러번 주차장에 들어올 수 있다는것이다..

이 부분을 미처 고려하지 않아, 계속 답이 다르게 나와 꽤 오래걸렸다.

풀이 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <sstream>
#include <algorithm>
#include <iostream>

using namespace std;

unordered_map<string,string> cars;
unordered_map<int,int> total_times;
string car_num,car_time,action;
void calculate_times(string enter_time, string out_time, string car_num);
int convert_to_minute(string car_time);
vector<int> solution(vector<int> fees, vector<string> records) {
    vector<int> answer;
    for(string record : records){
        stringstream ss(record);
        ss >> car_time >> car_num >> action;
        if(action == "IN"){
            cars[car_num] = car_time;
        }
        else if(action =="OUT"){
            if(cars.find(car_num) != cars.end()){
                calculate_times(cars[car_num], car_time, car_num);
                cars.erase(car_num);
            }
        }
    }
    
    if(!cars.empty()){
        for(const auto &pair : cars){
            const string &car_num = pair.first;
            const string &enter_time = pair.second;
            calculate_times(enter_time, "23:59", car_num);
        }
        cars.clear();
    }
    
    vector<pair<int,int>> sorted_cars (total_times.begin(), total_times.end());
    sort(sorted_cars.begin(), sorted_cars.end());
    
    for(int i=0; i<sorted_cars.size(); i++){
        int bill = 0;
        //기본요금 이하면 기본요금 청구
        if(sorted_cars[i].second <= fees[0]){
            answer.push_back(fees[1]);
        }
        else{
            int extra_time = sorted_cars[i].second - fees[0]; // 초과 시간
            int extra_fee = ((extra_time + fees[2] - 1) / fees[2]) * fees[3]; // 올림 처리
            bill = fees[1] + extra_fee; // 기본 요금 + 초과 요금
            answer.push_back(bill);
        }
    }
    
    return answer;
}
void calculate_times(string enter_time, string out_time, string car_num){
    int e_time = convert_to_minute(enter_time);
    int o_time = convert_to_minute(out_time);
    int c_num = stoi(car_num);
    total_times[c_num] += o_time - e_time;
}
int convert_to_minute(string car_time){
    int hour = stoi(car_time.substr(0,2));
    int minute = stoi(car_time.substr(3,2));
    // cout << "hour : " << hour <<'\n';
    // cout << "minute :" << minute << '\n';
    
    return hour*60 + minute;
}