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

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

🎯 문제 접근

주차장의 입차(IN)와 출차(OUT) 기록을 바탕으로 차량별 주차 요금을 정산하는 시뮬레이션 문제이다.
이 문제의 핵심은 시간 누적 로직과 예외 케이스(출차 기록 없음) 그리고 올림(Ceiling) 처리를 얼마나 정확하게 구현하느냐이다.

차량 번호는 0000부터 9999까지로 고정되어 있고, 결과는 차량 번호가 작은 순서대로 반환해야 한다. 따라서 별도의 정렬(Sort) 과정을 거치는 대신, 크기가 10,000인 배열을 사용한 직접 접근(Direct Access) 방식을 사용하면 $O(N)$의 매우 빠른 속도로 문제를 해결할 수 있다.

자료구조 선택:

• Car[] cars: 인덱스가 곧 차량 번호가 되는 객체 배열 (크기 10,000).
• Car 클래스: 각 차량의 최근 입차 시간(inTime)과 누적 주차 시간(accumulate)을 상태로 관리합니다.

📋 문제 조건

1. 입/출차 기록: 시각(HH:MM), 차량번호(4자리), 내역(IN/OUT).
2. 누적 시간 계산:
   • OUT 기록이 있으면: 출차 시각 - 입차 시각을 누적.
   • OUT 기록이 없으면: 23:59에 출차한 것으로 간주하여 누적.
3. 요금 계산 공식:
   • 기본 시간 이내: 기본 요금
   • 기본 시간 초과: 기본 요금 + ⌈(초과 시간 / 단위 시간)⌉ x 단위 요금
   • 주의: 초과 시간이 단위 시간으로 나누어 떨어지지 않으면 올림 처리.
4. 출력: 차량 번호가 작은 자동차부터 순서대로 요금을 담아 반환.

🔎 문제 설계

1. 자료구조 및 헬퍼 함수

• class Car:
  • int inTime: 현재 주차 중이면 입차 시각(분), 주차장에 없으면 -1.
  • int accumulate: 하루 동안의 총 누적 주차 시간.
• convertTime(String time): "HH:MM" 문자열을 분(int) 단위로 변환 (HH * 60 + MM).
• calculator(int time): 문제의 요금표에 따라 최종 요금을 계산. Math.ceil을 사용하여 올림 처리를 정확히 수행.

2. 전체 프로세스 (Solution 함수)

1. 초기화: Car[10000] 배열을 생성한다.
2. 기록 순회 (Parsing & Processing):
   • IN: 해당 차량(cars[번호]) 객체가 없으면 생성(new Car(-1, 0))하고, inTime에 현재 시각을 기록한다.
   • OUT: (현재 시각 - inTime)을 accumulate에 더하고, inTime을 -1로 변경하여 출차 상태임을 명시한다.
3. 자정(23:59) 정산 (Post-Processing):
   • 배열 전체를 순회하며 inTime != -1인 차량(입차 후 출차 안 한 차)을 찾는다.
   • 23:59 (1439분) - inTime을 계산하여 accumulate에 추가한다.
4. 요금 계산 및 결과 반환:
   • 배열 인덱스 0부터 9999까지 순회하므로 별도의 정렬이 필요 없다.
   • calculator 함수로 요금을 계산하여 결과 배열에 담는다.

3. 주의할 점 (Logical Pitfalls)

• 객체 재사용: 차량이 재입차 할 때 new Car()를 다시 호출하면 기존 누적 시간이 초기화되므로 주의해야 한다. (if (cars[i] == null) 체크 필수)
• 유령 주차 방지: 출차(OUT) 처리 시 inTime을 단순히 갱신하는 게 아니라, -1과 같은 특수 값으로 변경하여 "주차장에 없음"을 명확히 표시해야 23:59 일괄 정산 때 중복 계산을 막을 수 있다.

📈 시간복잡도 분석

• N: records의 길이 (최대 1,000)
• K: 차량 번호의 범위 (상수 10,000)

1. 기록 순회: 모든 기록을 한 번씩 읽고 처리하므로 $O(N)$.
2. 일괄 정산 및 요금 계산: 크기가 10,000인 배열을 순회하므로 $O(K)$.
3. 최종 시간 복잡도: $O(N + K)$.
   • $N$과 $K$ 모두 매우 작으므로 사실상 상수 시간에 가깝게 동작한다. 배열 인덱스로 직접 접근하기 때문에 Map을 사용하는 $O(N \log N)$ 방식보다 이론적으로 더 빠르다.

💻 구현 코드

import java.util.*;

class Solution {            
    
    // 차량의 상태를 관리하는 클래스
    static class Car {
        int inTime;       // 입차 시각 (주차장에 없으면 -1)
        int accumulate;   // 누적 주차 시간
        
        public Car(int inTime, int accumulate) {
            this.inTime = inTime;
            this.accumulate = accumulate;
        }
    }
    
    // 차량 번호(0000~9999)를 인덱스로 활용 (Direct Access)
    Car[] cars = new Car[10000];
    
    // "HH:MM" -> 분(int) 변환
    public int convertTime(String time) {
        String[] timeArr = time.split(":");        
        int hour = Integer.parseInt(timeArr[0]);
        int minute = Integer.parseInt(timeArr[1]);
        return hour * 60 + minute;
    }
    
    // 요금 계산 (올림 처리 포함)
    public int calculator(int[] fees, int accumulate) {
        if (accumulate <= fees[0]) {
            return fees[1];
        } else {
            int overTime = accumulate - fees[0];
            // Math.ceil을 사용하여 올림 처리
            int unit = (int) Math.ceil((double) overTime / fees[2]);
            return fees[1] + unit * fees[3];
        }
    }
    
    public int[] solution(int[] fees, String[] records) {
        cars = new Car[10000]; // 배열 초기화
        
        for (String record: records) {
            String[] tmp = record.split(" ");
            int time = convertTime(tmp[0]);
            int carNo = Integer.parseInt(tmp[1]);
            
            // 처음 방문한 차량이면 객체 생성
            if (cars[carNo] == null) {
                cars[carNo] = new Car(-1, 0);
            }
            
            if (tmp[2].equals("IN")) {
                cars[carNo].inTime = time;
            } else {
                // OUT: 누적 시간 계산 후 상태를 -1(부재중)로 변경
                cars[carNo].accumulate += time - cars[carNo].inTime;
                cars[carNo].inTime = -1; 
            }
        }
                
        int carCnt = 0;
        // 23:59 일괄 정산 (아직 나가지 않은 차들 처리)
        for (int i = 0; i < 10000; i++) {
            if (cars[i] != null) {
                carCnt++;
                if (cars[i].inTime != -1) {
                    cars[i].accumulate += (23 * 60 + 59) - cars[i].inTime;
                }
            }
        }
        
        // 결과 배열 생성 (차량 번호 순서대로 담김)
        int[] answer = new int[carCnt];
        int idx = 0;
        
        for (int i = 0; i < 10000; i++) {
            if (cars[i] == null) continue;
            answer[idx++] = calculator(fees, cars[i].accumulate);
        }
            
        return answer;
    }
}