vector 대신 set

[2022 KAKAO BLIND RECRUITMENT 주차 요금 계산]
문제를 풀다가, 개선의 여지가 있는 부분이 있는지 살펴보았다.

<내 코드>

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

using namespace std;

int convert(string time){
    string str;
    int min = 0;
    
    for(int i=0; i<time.length(); i++)
    {
        if(time[i] == ':')
        {
            min = stoi(str) * 60; // 시
            str = "";
        }
        else
            str += time[i];
    }
    min += stoi(str); // 분
    
    return min;
}

vector<int> solution(vector<int> fees, vector<string> records) {
    vector<int> answer;
    map<string, int> charge_fee; // [["5961", 1250], ...] 차량번호, 요금
    map<string, int> total_time; // [["5961", 120], ...] 차량번호, 누적 주차시간
    // 차례로 배열에 넣다가 이미 있는 번호판이면 시간 계산 후
    // 배열에 있던 것 빼고 set으로 [번호, 청구요금] 저장
    // set을 돌면서 answer에 넣기
    map<string, string> mp; // [["5961", "05:34"], ...] 어차피 먼저 들어가있는 건 IN일테니
    vector<string> car_num; // IN OUT판별 위한 차량번호 배열
    int fee = 0;
    for(auto rc: records)
    {
        // 공백 기준으로 나눠서 배열로 저장
        vector<string> ss; // ["05:34", "5961", "IN"]
        string str = "";
        for(int i=0; i<rc.length(); i++)
        {
            if(rc[i] == ' ')
            {
                ss.push_back(str);
                str = "";
            }
            else
                str += rc[i];
        }
        ss.push_back(str); // IN/OUT 추가
        
        // 조건 계산
        if(find(car_num.begin(), car_num.end(), ss[1]) == car_num.end()) // 못 찾으면
        {
            mp[ss[1]] = ss[0]; // IN 저장
            // 차 번호만 따로 저장 (비교 위해)
            car_num.push_back(ss[1]);
        }
        else // 찾으면
        {
            car_num.erase(remove(car_num.begin(), car_num.end(), ss[1]), car_num.end());
            // 누적 주차 시간이 기본 시간 이하일 경우
            int parking = convert(ss[0]) - convert(mp[ss[1]]); // OUT - IN
            total_time[ss[1]] += parking;
            charge_fee[ss[1]] = 0; // 생성
        }
    }
    if(!car_num.empty()) // 출차 내역이 없는 차량들이 있다면
    {
        for(auto c: car_num)
        {
            int parking = convert("23:59") - convert(mp[c]);
            total_time[c] += parking;
            charge_fee[c] = 0; // 생성
        }
    }
    
    for(auto &res: charge_fee)
    {
        string num = res.first; // 차량번호
        cout << res.first << "의 누적 주차 시간: " << total_time[num] << endl;
        if(total_time[num] <= fees[0])
        {
            charge_fee[num] = fees[1];
        }
        // 기본 시간을 초과했을 경우
        else
        {
            int exceed = total_time[num]-fees[0];
            charge_fee[num] = fees[1] + ceil((double)exceed / fees[2]) * fees[3];
        }
        
        answer.push_back(res.second);
    }
    
    // 차량번호가 작은 자동차부터 청구할 주차요금 차례로 리턴
    return answer;
}

여기서

1. vector<string> car_num 대신 set<string> 사용하기

현재는 차량이 IN 상태인지 확인하기 위해 find()와 erase()를 사용하지만,
vector의 find + erase는 O(N)
set을 쓰면 insert, find, erase 모두 O(log N)로 더 효율적이다.

2. mp에서도 똑같이 차량번호를 key값으로 사용하므로 car_num을 중복으로 사용하지 않아도 된다.

3. 시간을 분으로 바꾸는 convert함수도 다음처럼 substr을 활용해서 간단하게 작성할 수 있다.

int convert(string time) {
    return stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2));
}

<최적화한 코드>

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <iostream>

using namespace std;

int convert(string time) {
    return stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2));
}

vector<int> solution(vector<int> fees, vector<string> records) {
    vector<int> answer;
    map<string, int> charge_fee;   // 차량별 요금
    map<string, int> total_time;   // 차량별 누적 주차 시간
    map<string, int> in_time_map;  // 차량별 마지막 입차 시간

    for (const string& record : records) {
        string time = record.substr(0, 5);
        string car = record.substr(6, 4);
        string state = record.substr(11);

        int minutes = convert(time);

        if (state == "IN") {
            in_time_map[car] = minutes;  // IN 시간 저장
        } else if (state == "OUT") {
            int in_time = in_time_map[car];
            total_time[car] += (minutes - in_time);
            in_time_map.erase(car);  // 처리 완료 후 제거
        }
    }

    // 출차 내역 없는 차량은 23:59에 자동 출차 처리
    for (auto& entry : in_time_map) {
        total_time[entry.first] += (convert("23:59") - entry.second);
    }

    // 요금 계산
    for (auto& entry : total_time) {
        string car = entry.first;
        int time = entry.second;
        if (time <= fees[0]) {
            charge_fee[car] = fees[1];
        } else {
            charge_fee[car] = fees[1] + 
                ceil((double)(time - fees[0]) / fees[2]) * fees[3];
        }
    }

    // 차량 번호 순으로 요금 반환
    for (auto& entry : charge_fee) {
        answer.push_back(entry.second);
    }

    return answer;
}