프로그래머스 92341 - 주차 요금 계산 (Lv.5)

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

// 프로그래머스 92341 - 주차 요금 계산 (Lv.5)
// https://school.programmers.co.kr/learn/courses/30/lessons/92341

// 문제 설명
// 요금표 fees = [기본시간(분), 기본요금(원), 단위시간(분), 단위요금(원)] 과
// "HH:MM 차량번호 IN/OUT" 형식의 입출차 기록 records가 주어진다.
// 차량별 누적 주차 시간으로 요금을 계산해 차량번호 오름차순으로 반환하라.
// 출차 기록이 없는 차량은 23:59에 출차한 것으로 본다.

// 제약 조건
// fees 길이 4, 1 <= 기본시간/단위시간 <= 1439, 0 <= 기본요금 <= 100,000, 1 <= 단위요금 <= 10,000
// 1 <= records 길이 <= 1,000, 차량번호는 4자리 숫자, 잘못된 입력은 주어지지 않는다
// 누적 시간 <= 기본시간 이면 기본요금
// 초과하면 기본요금 + ceil((누적 - 기본시간) / 단위시간) * 단위요금

// Example
// Input : fees = [180,5000,10,600],
//         records = ["05:34 5961 IN","06:00 0000 IN","06:34 0000 OUT","07:59 5961 OUT",
//                    "07:59 0148 IN","18:59 0000 IN","19:09 0148 OUT","22:59 5961 IN","23:00 5961 OUT"]
// Output: [14600, 34400, 5000]   (0000=334분, 0148=670분, 5961=146분)
//
// Input : fees = [120,0,60,591], records = ["16:00 3961 IN","16:00 0202 IN",
//                 "18:00 3961 OUT","18:00 0202 OUT","23:58 3961 IN"]
// Output: [0, 591]               (0202=120분 → 기본요금 0, 3961=120+1=121분 → 1단위 초과)
//
// Input : fees = [1,461,1,10], records = ["00:00 1234 IN"]
// Output: [14841]                (미출차 → 23:59, 1439분)

// 접근 — 시각을 분으로 정규화한 시뮬레이션 + map 자동 정렬
// 1) "HH:MM"을 분 단위 int로 바꿔 시/분 경계 계산을 없앤다.
// 2) inTime: 아직 안 나간 차량의 입차 시각. OUT을 만나면 차이를 total에 더하고 지운다.
// 3) 기록을 다 읽고 inTime에 남은 차량은 23:59(1439분)까지 주차한 것으로 정산.
// 4) map<string,int>는 키 순으로 순회한다. 차량번호가 4자리 0채움 문자열이라
//    사전순 == 번호 오름차순이므로 별도 정렬이 필요 없다.
// 5) 초과분 올림은 실수 ceil 대신 (a + b - 1) / b 정수 연산으로 처리.
// 시간 O(m log m) (m = records 길이), 공간 O(차량 수)

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

using namespace std;

// "HH:MM" → 자정부터 지난 분
int toMin(const string& t) {
    return (t[0] - '0') * 600 + (t[1] - '0') * 60 + (t[3] - '0') * 10 + (t[4] - '0');
}

vector<int> solution(vector<int> fees, vector<string> records) {
    map<string, int> inTime;                       // 차량번호 → 입차 시각(미출차 상태)
    map<string, int> total;                        // 차량번호 → 누적 주차 시간(분)

    for (auto& r : records) {
        string car = r.substr(6, 4), act = r.substr(11);
        int t = toMin(r.substr(0, 5));
        if (act == "IN") inTime[car] = t;
        else {
            total[car] += t - inTime[car];
            inTime.erase(car);                     // 출차 처리 완료 — 미출차 목록에서 제거
        }
    }
    for (auto& [car, t] : inTime) total[car] += 1439 - t;   // 남은 차량은 23:59 출차

    vector<int> answer;
    for (auto& [car, t] : total) {                 // map이라 차량번호 오름차순으로 순회
        int fee = fees[1];
        if (t > fees[0])
            fee += ((t - fees[0]) + fees[2] - 1) / fees[2] * fees[3];   // 정수 올림
        answer.push_back(fee);
    }
    return answer;
}

정리

• 구현 문제의 난이도는 알고리즘이 아니라 상태를 어떻게 쪼개느냐에서 나온다. 여기서는 inTime(아직 안 나간 차 = 진행 중 상태)과 total(정산 끝난 누적 시간 = 확정 상태)을 다른 자료구조로 분리한 게 전부다. 하나의 map에 “입차 시각도 누적 시간도” 담으려 하면 미출차 판정에 -1 같은 센티널이 필요해지고 그 센티널이 요금 계산까지 새어나간다.
• inTime을 OUT에서 erase하기 때문에 기록을 다 읽은 뒤 남아 있는 키가 곧 미출차 차량 목록이 된다. “출차 기록이 없는 차량은 23:59” 규칙을 위한 별도 검사·별도 컨테이너가 필요 없다 — 상태를 지우는 것 자체가 목록 관리다.
• 시각은 문자열에서 바로 분 단위 int로 정규화한다. HH:MM 두 개를 비교·감산하려면 시 자리 차이와 분 자리 차이를 따로 다뤄야 하는데, HH*60 + MM으로 접으면 주차 시간이 그냥 뺄셈 하나다. 인덱스 위치가 고정(HH:MM 5글자)이라 t[0]*600 + t[1]*60 + t[3]*10 + t[4]처럼 c - '0' 변환을 직접 펴 써도 안전하다.
• map<string,int>의 정렬이 요구사항을 그대로 만족한다. 차량번호가 4자리 0채움 문자열이라 "0148" < "0202" < "5961"처럼 사전순이 번호 오름차순과 일치한다 — 결과를 모아 sort하는 단계가 통째로 사라진다. 만약 번호가 0채움이 아니었다면("148" vs "99") 사전순이 깨져서 int로 바꿔 정렬해야 했다. 정렬을 컨테이너에 맡기려면 키 표현이 정렬 순서를 보존하는지 먼저 확인한다.
• 올림은 ceil((double)a / b) 대신 (a + b - 1) / b 정수 연산으로 쓴다. 이 범위(피제수 최대 1438)에서는 실수 ceil도 결과가 같지만, 요금은 정확히 맞아야 하는 값이고 정수 나눗셈이 애초에 내림이라 분자에 b - 1만 더하면 올림이 된다 — 캐스팅도 헤더도 필요 없다. 상한도 점검해두면 최악 요금이 461 + 1438 * 10,000 ≈ 1.4 x 10^7로 int 범위 안이다.
• 경계 규칙 두 개가 예제로 직접 검증된다. 예제 2의 0202는 정확히 기본시간(120분) 이라 초과가 아니고(t > fees[0], >=가 아니다), 3961은 121분으로 단 1분 초과인데도 한 단위 요금 591원이 붙는다 — “딱 맞으면 기본요금, 1분만 넘겨도 한 단위” 가 부등호 방향과 올림 두 곳에 각각 걸려 있다.
• 검증: 예제 3개([14600,34400,5000], [0,591], [14841]) 통과 (MSVC /std:c++17 컴파일·실행). 커리큘럼 96번.

핵심 요약 — 진행 중 상태(inTime)와 확정 상태(total)를 다른 map으로 분리하면 미출차 센티널이 사라지고, 남은 키가 곧 미출차 목록이 된다. 차량번호가 4자리 0채움이라 map<string,int>의 사전순이 번호 오름차순과 일치해 정렬 단계가 통째로 없어지고, 요금 올림은 부동소수점 없이 (a + b - 1) / b로 처리한다.