[프로그래머스/Java] 주차 요금 계산

문제 설명

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

프로그래머스

주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다.

• 요금표

기본 시간(분)	기본 요금(원)	단위 시간(분)	단위 요금(원)
180	5000	10	600

• 입/출차 기록

시각(시:분)	차량 번호	내역
05:34	5961	입차
06:00	0000	입차
06:34	0000	출차
07:59	5961	출차
07:59	0148	입차
18:59	0000	입차
19:09	0148	출차
22:59	5961	입차
23:00	5961	출차

• 자동차별 주차 요금

차량 번호	누적 주차 시간(분)	주차 요금(원)
0000	34 + 300 = 334	5000 + ⌈(334 - 180) / 10⌉ x 600 = 14600
0148	670	5000 + ⌈(670 - 180) / 10⌉ x 600 = 34400
5961	145 + 1 = 146	5000

• 어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주합니다.
  • 0000번 차량은 18:59에 입차된 이후, 출차된 내역이 없습니다. 따라서, 23:59에 출차된 것으로 간주합니다.
• 00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산합니다.
• 누적 주차 시간이 기본 시간이하라면, 기본요금을 청구합니다.
• 누적 주차 시간이 기본 시간을 초과하면, 기본 요금에 더해서, 초과한 시간에 대해서 단위 시간마다단위 요금을 청구합니다.
  • 초과한 시간이 단위 시간으로 나누어 떨어지지 않으면, 올림 합니다.
  • ⌈a⌉ : a보다 작지 않은 최소의 정수를 의미합니다. 즉, 올림을 의미합니다.

주차 요금을 나타내는 정수 배열 fees, 자동차의 입/출차 내역을 나타내는 문자열 배열 records가 매개변수로 주어집니다. 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• fees의 길이 = 4
  • fees[0] = 기본 시간(분)
  • 1 ≤ fees[0] ≤ 1,439
  • fees[1] = 기본요금(원)
  • 0 ≤ fees[1] ≤ 100,000
  • fees[2] = 단위 시간(분)
  • 1 ≤ fees[2] ≤ 1,439
  • fees[3] = 단위 요금(원)
  • 1 ≤ fees[3] ≤ 10,000
• 1 ≤ records의 길이 ≤ 1,000
  • records의 각 원소는 "시각 차량번호 내역" 형식의 문자열입니다.
  • 시각, 차량번호, 내역은 하나의 공백으로 구분되어 있습니다.
  • 시각은 차량이 입차되거나 출차된 시각을 나타내며, HH:MM 형식의 길이 5인 문자열입니다.
    • HH:MM은 00:00부터 23:59까지 주어집니다.
    • 잘못된 시각("25:22", "09:65" 등)은 입력으로 주어지지 않습니다.
  • 차량번호는 자동차를 구분하기 위한, `0'~'9'로 구성된 길이 4인 문자열입니다.
  • 내역은 길이 2 또는 3인 문자열로, IN 또는 OUT입니다. IN은 입차를, OUT은 출차를 의미합니다.
  • records의 원소들은 시각을 기준으로 오름차순으로 정렬되어 주어집니다.
  • records는 하루 동안의 입/출차된 기록만 담고 있으며, 입차된 차량이 다음날 출차되는 경우는 입력으로 주어지지 않습니다.
  • 같은 시각에, 같은 차량번호의 내역이 2번 이상 나타내지 않습니다.
  • 마지막 시각(23:59)에 입차되는 경우는 입력으로 주어지지 않습니다.
  • 아래의 예를 포함하여, 잘못된 입력은 주어지지 않습니다.
    • 주차장에 없는 차량이 출차되는 경우
    • 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우

입출력 예

fees	records	result
[180, 5000, 10, 600]	["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"]	[14600, 34400, 5000]
[120, 0, 60, 591]	["16:00 3961 IN","16:00 0202 IN","18:00 3961 OUT","18:00 0202 OUT","23:58 3961 IN"]	[0, 591]
[1, 461, 1, 10]	["00:00 1234 IN"]	[14841]

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 요금표

기본 시간(분)	기본 요금(원)	단위 시간(분)	단위 요금(원)
120	0	60	591

• 입/출차 기록

시각(시:분)	차량 번호	내역
16:00	3961	입차
16:00	0202	입차
18:00	3961	출차
18:00	0202	출차
23:58	3961	입차

• 자동차별 주차 요금

차량 번호	누적 주차 시간(분)	주차 요금(원)
0202	120	0
3961	120 + 1 = 121	0 +⌈(121 - 120) / 60⌉x 591 = 591

• 3961번 차량은 2번째 입차된 후에는 출차된 내역이 없으므로, 23:59에 출차되었다고 간주합니다.

입출력 예 #3

• 요금표

기본 시간(분)	기본 요금(원)	단위 시간(분)	단위 요금(원)
1	461	1	10

• 입/출차 기록

시각(시:분)	차량 번호	내역
00:00	1234	입차

• 자동차별 주차 요금

차량 번호	누적 주차 시간(분)	주차 요금(원)
1234	1439	461 +⌈(1439 - 1) / 1⌉x 10 = 14841

• 1234번 차량은 출차 내역이 없으므로, 23:59에 출차되었다고 간주합니다.

 

내가 작성한 코드

import java.util.*;

class Solution {
    public int[] solution(int[] fees, String[] records) {
        // 차량 입차 시간을 저장하는 Map (현재 주차 중인 차량)
        Map<String, Integer> inMap = new HashMap<>();
        // 차량별 누적 주차 시간을 저장하는 Map
        Map<String, Integer> accMap = new HashMap<>();
        
        // 주차 기록 순회
        for (String record : records) {
            // 공백 기준으로 시간, 차량번호, 입/출차 상태 분리
            String[] s = record.split("\\s+");
            // 시간을 "분" 단위로 변환
            int m = toMinutes(s[0]);
            String car = s[1];
            String io = s[2];
            
            // 입차(IN)인 경우 -> 입차 시각 기록
            if (io.equals("IN")) {
                inMap.put(car, m);
            // 출차(OUT)인 경우 -> 누적 주차 시간 계산 후 제거
            } else {
                // Map에서 제거하면서 입차 시각 변환
                int min = inMap.remove(car);
                // (출차 시각 - 입차 시각)을 누적 주차 시간에 더함
                accMap.put(car, accMap.getOrDefault(car, 0) + (m - min));
            }
        }
        
        // 출차하지 않은 차량 처리 (23:59 기준으로 정산)
        for (Map.Entry<String, Integer> e : inMap.entrySet()) {
            String car = e.getKey();
            int in = e.getValue();
            // 23:59(=1439분)까지 주차한 것으로 계산
            accMap.put(car, accMap.getOrDefault(car, 0) + (1439 - in));
        }
        
        // 차량 번호 기준 오름차순 정렬
        List<String> cars = new ArrayList<>(accMap.keySet());
        Collections.sort(cars);
        
        int[] answer = new int[cars.size()];
        
        // 각 차량별 최종 요금 계산
        for (int i = 0; i < cars.size(); i++) {
            // 총 주차 시간(분)
            int minutes = accMap.get(cars.get(i));
            
            // 기본 시간 이하라면 기본 요금만 부과
            if (minutes <= fees[0]) {
                answer[i] = fees[1];
                continue;
            }
            
            // 초과한 시간 계산
            int extra = minutes - fees[0];
            // 단위 시간
            int unitT = fees[2];
            // 단위 요금
            int unitC = fees[3];
            
            // 추가 단위 계산
            // ex) 단위시간 10분, 초과시간 11분 -> (11 + 10 - 1) / 10 = 2단위
            int units = (extra + unitT - 1) / unitT;
            // 총 요금 = 기본 요금 + (단위 요금 * 단위수)
            int total = fees[1] + units * unitC;
            
            answer[i] = total;
        }
        
        // 차량번호 오름차순으로 계산된 요금 배열 반환
        return answer;
    }
    
    // "HH:MM" 형태의 시간을 "분" 단위로 변환하는 메서드
    private int toMinutes(String time) {
        String[] t = time.split(":");
        int hour = Integer.parseInt(t[0]);
        int minute = Integer.parseInt(t[1]);
        
        return hour * 60 + minute;
    }
}

문제를 풀기 위해 생각한 방향

처음 문제를 봤을 때, 차량의 입출차 기록을 분석하여 각 차량별로 최종 주차 요금을 계산해야 하는 문제임을 파악했다. 단순히 입차(IN)와 출차(OUT)만 구분하는 것이 아니라, 출차 기록이 없는 차량의 경우 23:59까지 주차했다고 간주해야 하며, 누적된 주차 시간에 따라 요금을 계산하는 것이 핵심이었다.

조건을 분석해 보면, 각 기록은 "시각 차량번호 IN/OUT" 형식으로 주어지며, 동일한 차량이 여러 번 입출차할 수 있다. 따라서 한 번의 입출차만으로 계산할 수 없고, 차량별로 누적 주차 시간을 저장해야 했다. 또한 최종 요금 계산 시에는 기본요금, 단위 시간, 단위 요금을 기준으로 초과 시간을 올림(Math.ceil) 처리해야 한다는 점도 주의해야 했다.

이 문제를 해결하기 위해, 각 차량의 입차 시각을 저장하는 Map<String, Integer>(inMap)과 차량별 누적 주차 시간을 저장하는 Map<String, Integer>(accMap)을 사용하기로 했다. inMap에는 현재 주차 중인 차량의 입차 시각을 저장하고, 출차 시점이 오면 remove()를 이용해 입차 시간을 꺼내고 누적 주차 시간(accMap)에 더했다. 이렇게 하면 입출차를 깔끔하게 처리할 수 있었고, 출차하지 않은 차량은 반복문을 돌며 23:59(=1439분)까지의 시간을 더해 최종 누적 시간을 완성했다.

시간 계산은 “HH:MM” 형태를 분 단위로 변환하는 toMinutes() 메서드를 별도로 만들어 처리했다. 이 덕분에 시각 계산이 단순해졌고, 출차 시간에서 입차 시간을 뺄 때 직관적으로 이해할 수 있었다. 이후 차량 번호를 오름차순으로 정렬해 결과 배열에 담았으며, 요금 계산 시에는 기본 시간을 초과한 부분에 대해 (초과시간 + 단위시간 - 1) / 단위시간 공식을 활용해 정수 연산으로 올림 계산을 수행했다.

전체적으로 이 문제는 문자열 파싱, 해시맵을 이용한 누적 관리, 올림 계산이라는 세 가지 요소가 핵심이었다. 시간복잡도는 O(N log N)으로, N은 records의 길이이며, 차량 번호 정렬 단계에서 log N이 추가된다. 각 차량의 입출차 기록을 맵에서 관리하기 때문에 탐색과 갱신은 모두 평균적으로 O(1)에 가까워 효율적으로 처리된다.

결과적으로, 이 문제는 단순한 시뮬레이션 문제이지만 “출차 누락 차량 처리”와 “요금 올림 계산” 부분에서 세밀한 구현이 필요한 문제였다.
이 과정을 통해 문자열 파싱과 Map 자료구조를 활용한 누적 계산의 중요성을 다시 한번 느낄 수 있었다.