catsridingCATSRIDING|OCEANWAVES
Challenges

프로그래머스 | Level 2 | 주차 요금 계산

jynn@catsriding.com
Aug 13, 2024
Published byJynn
999
프로그래머스 | Level 2 | 주차 요금 계산

Programmers | Level 2 | 주차 요금 계산

Problems

󰧭 Description

주차 요금을 계산하는 문제입니다. 각 차량이 입차와 출차된 시간을 기록한 records[] 배열과 요금표를 나타내는 fees[] 배열이 주어집니다. 차량이 주차된 총 시간을 계산하고, 요금표에 따라 각 차량의 주차 요금을 계산해야 합니다. 요금 계산은 다음 규칙을 따릅니다:

  • 주어진 기본 시간 이내의 주차는 기본 요금을 부과합니다.
  • 기본 시간을 초과한 주차는 초과 시간에 따라 단위 요금을 부과합니다.
  • 차량이 출차된 기록이 없으면, 23:59에 출차된 것으로 간주합니다.

 Constraints

  • fees[]의 길이 = 4
    • fees[0] = 기본 시간(분)
    • fees[1] = 기본 요금(원)
    • fees[2] = 단위 시간(분)
    • fees[3] = 단위 요금(원)
  • 1 ≤ records[]의 길이 ≤ 1,000
  • 기록된 시각은 HH:MM 형식의 문자열입니다.
  • 차량 번호는 길이 4인 문자열로 주어집니다.
  • 모든 시각은 하루 내에 발생합니다 (00:00 ~ 23:59).
  • 동일한 차량 번호의 기록이 중복되지 않습니다.

󰦕 Examples

feesrecordsresult
[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]

Solutions

󰘦 Code

Solution.java
import java.util.*;
import java.time.*;

class Solution {
    public int[] solution(int[] fees, String[] records) {
        // 각 차량의 입차 시각을 저장하는 맵
        Map<String, LocalTime> inTimes = new HashMap<>();
        // 각 차량의 누적 주차 시간을 저장하는 맵 (차량 번호 기준으로 정렬)
        Map<String, Integer> parkingTimes = new TreeMap<>();
        
        // 입출차 기록을 순차적으로 처리
        for (String record : records) {
            String[] fields = record.split(" ");  // 공백을 기준으로 시각, 차량 번호, 입출차 유형으로 분리
            String time = fields[0];  // 입출차 시각 (HH:MM)
            String car = fields[1];   // 차량 번호
            String type = fields[2];  // IN 또는 OUT
            
            LocalTime now = LocalTime.parse(time); // 현재 시각을 LocalTime 객체로 변환
            // 입차 시
            if (type.equals("IN")) { 
                inTimes.put(car, now); // 차량 번호와 입차 시각을 inTimes 맵에 기록
            }
            // 출차 시
            if (type.equals("OUT")) { 
                LocalTime in = inTimes.get(car); // 입차 시각 가져오기
                int duration = (int) Duration.between(in, now).toMinutes(); // 입차 시각과 출차 시각의 차이를 분 단위로 계산
                parkingTimes.put(car, parkingTimes.getOrDefault(car, 0) + duration); // 누적 주차 시간 갱신
                inTimes.remove(car); // 출차 처리 후, 해당 차량의 입차 시각 삭제
            } 
        }
        
        // 출차 기록이 없는 차량 처리
        for(Map.Entry<String, LocalTime> entry : inTimes.entrySet()) {
            String car = entry.getKey();
            LocalTime in = entry.getValue();
            int duration = (int) Duration.between(in, LocalTime.of(23, 59)).toMinutes();
            parkingTimes.put(car, parkingTimes.getOrDefault(car, 0) + duration);
        }
        
        // 요금 계산
        int baseTime = fees[0];
        int baseFee = fees[1];
        int unitTime = fees[2];
        int unitFee = fees[3];
        List<Integer> results = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : parkingTimes.entrySet()) {
            int parkingTime = entry.getValue() - baseTime;
            parkingTime = parkingTime < 0 ? 0 : parkingTime;
            int fee = baseFee + (int) Math.ceil((double) parkingTime / unitTime) * unitFee;
            results.add(fee);
        }
        
        return results.stream().mapToInt(Integer::intValue).toArray();
    }
}

 Approaches

이 문제는 입출차 기록을 기반으로 주차 요금을 계산하는 과정을 단계별로 살펴보는 시뮬레이션 문제입니다. 문제의 요구사항에 따라 차량별로 주차 시간을 계산하고, 주어진 요금표에 맞춰 주차 요금을 산출해야 합니다. 아래에 각 단계를 구체적으로 설명하겠습니다.

1. 입출차 기록 분석 및 데이터 초기화

주어진 입출차 기록 records[]을 분석하여, 각 차량의 입차와 출차 시간을 관리합니다. 이를 위해 차량별 입차 시각을 저장하는 inTimes 맵과, 누적 주차 시간을 계산할 parkingTimes 맵을 초기화합니다.

Solution.java
// 각 차량의 입차 시각을 저장하는 맵
Map<String, LocalTime> inTimes = new HashMap<>();
// 각 차량의 누적 주차 시간을 저장하는 맵 (차량 번호 기준으로 정렬)
Map<String, Integer> parkingTimes = new TreeMap<>();
  • inTimes: 차량 번호를 키로 하여 해당 차량의 입차 시각을 기록합니다. HashMap을 사용하여 빠른 조회가 가능하며, 출차 시 이 맵에서 입차 시각을 조회하여 주차 시간을 계산합니다.
  • parkingTimes: 각 차량의 누적 주차 시간을 저장합니다. 차량 번호를 기준으로 결과를 정렬해야 하므로 TreeMap을 사용합니다. TreeMap은 키를 자동으로 정렬된 상태로 유지하며, 이진 탐색 트리 기반의 자료 구조로 O(log n)의 시간 복잡도로 데이터를 삽입, 삭제, 탐색할 수 있는 특성을 가집니다. 따라서, 요금 계산 후 결과를 차량 번호 순서대로 정렬된 상태로 바로 반환할 수 있습니다.

TreeMap이 떠오르지 않거나, 또는 다른 방법을 고려하고 싶다면 HashMap을 사용하여 데이터를 저장한 후, 키 값을 추출하여 정렬하는 방법도 있습니다. 이 방법에서는 HashMap에 데이터를 저장한 후, 키를 리스트로 변환하고 정렬한 다음, 정렬된 키를 기반으로 결과를 처리할 수 있습니다:

Solution.java
Map<String, Integer> map = new HashMap<>();
// Key 리스트 추출
List<String> keys = new ArrayList<>(map.keySet());
// Key 리스트 정렬
Collections.sort(keys);

// 정렬된 Key를 활용하여 순차적으로 Map 데이터 접근
for (String key : keys) {
    parkingTime.get(car);
    ...
}
2. 주차 시간 계산

이 단계에서는 각 차량의 입출차 기록을 분석합니다. 입차 시에는 입차 시각을 inTimes 맵에 저장하고, 출차 시에는 inTimes 맵에서 해당 차량의 입차 시각을 조회하여 주차 시간을 계산한 후, 이를 parkingTimes 맵에 누적합니다.

Solution.java
for (String record : records) {
    String[] fields = record.split(" ");  // 공백을 기준으로 시각, 차량 번호, 입출차 유형으로 분리
    String time = fields[0];  // 입출차 시각 (HH:MM)
    String car = fields[1];   // 차량 번호
    String type = fields[2];  // IN 또는 OUT
    
    LocalTime now = LocalTime.parse(time); // 현재 시각을 LocalTime 객체로 변환
    // 입차 시
    if (type.equals("IN")) {
        inTimes.put(car, now); // 차량 번호와 입차 시각을 inTimes 맵에 기록
    }
    // 출차 시
    if (type.equals("OUT")) {
        LocalTime in = inTimes.get(car); // 입차 시각 가져오기
        int duration = (int) Duration.between(in, now).toMinutes(); // 입차 시각과 출차 시각의 차이를 분 단위로 계산
        parkingTimes.put(car, parkingTimes.getOrDefault(car, 0) + duration); // 누적 주차 시간 갱신
        inTimes.remove(car); // 출차 처리 후, 해당 차량의 입차 시각 삭제
    } 
}
  • 입출차 기록 분리: 각 입출차 기록은 String.split() 메서드를 사용하여 공백을 기준으로 시각, 차량 번호, 입출차 유형으로 분리됩니다. 이를 통해 각 기록을 개별적으로 처리할 수 있습니다.
    • time: 입출차 시각을 나타내는 문자열로, HH:MM 형식입니다.
    • car: 차량 번호로, 각 차량을 식별하는 키 역할을 합니다.
    • type: 입차(IN) 또는 출차(OUT)를 나타내는 문자열입니다.
  • 현재 시각 변환: 시간 계산을 효율적으로 처리하기 위해 LocalTime.parse() 메서드를 사용하여 time 문자열을 LocalTime 객체로 변환합니다.
  • 입차 처리:
    • 입차 시, 차량 번호와 입차 시각을 inTimes 맵에 기록합니다.
    • 이 정보는 이후 출차 시, 주차 시간을 계산하는 데 사용됩니다.
  • 출차 처리:
    • 출차 시, inTimes 맵에서 해당 차량의 입차 시각을 가져옵니다. 이를 통해 주차 시간을 계산하는데, Duration.between() 메서드를 사용하여 입차 시각과 출차 시각 사이의 차이를 분 단위로 계산합니다.
    • 계산된 주차 시간은 parkingTimes 맵에 누적됩니다. Map.getOrDefault()를 사용하여, 기존 주차 시간이 없으면 0을 기본값으로 설정합니다.
    • 출차 처리가 완료된 후, inTimes 맵에서 해당 차량의 입차 기록을 삭제하여 메모리를 정리합니다.

이 과정은 입출차 기록이 모두 처리될 때까지 반복되며, 각 차량의 주차 시간이 parkingTimes 맵에 누적됩니다.

3. 미출차 차량 처리

입출차 기록을 모두 처리한 후에도 inTimes 맵에 남아 있는 차량은 출차 기록이 없는 차량입니다. 이 경우, 해당 차량의 출차 시각을 23:59로 간주하고 주차 시간을 계산하여 parkingTimes 맵에 반영합니다.

Solution.java
for(Map.Entry<String, LocalTime> entry : inTimes.entrySet()) {
    String car = entry.getKey();
    LocalTime in = entry.getValue();
    int duration = (int) Duration.between(in, LocalTime.of(23, 59)).toMinutes(); // 23:59 출차 간주
    parkingTimes.put(car, parkingTimes.getOrDefault(car, 0) + duration); // 누적 주차 시간 갱신
}
  • 미출차 차량 처리: inTimes에 남아 있는 차량들에 대해 23:59까지의 주차 시간을 계산하고, parkingTimes 맵에 반영합니다.
4. 주차 요금 계산

각 차량의 누적 주차 시간을 기준으로, 주어진 요금표에 따라 주차 요금을 계산합니다. 기본 시간을 초과한 경우, 초과 시간에 대해 단위 시간 요금을 추가로 부과합니다.

Solution.java
int baseTime = fees[0];
int baseFee = fees[1];
int unitTime = fees[2];
int unitFee = fees[3];
List<Integer> results = new ArrayList<>();
for (Map.Entry<String, Integer> entry : parkingTimes.entrySet()) {
    int parkingTime = entry.getValue() - baseTime;
    parkingTime = parkingTime < 0 ? 0 : parkingTime; // 기본 시간 이하의 주차 시간은 0으로 설정
    int fee = baseFee + (int) Math.ceil((double) parkingTime / unitTime) * unitFee; // 초과 시간 요금 계산
    results.add(fee);
}
  • 기본 요금 부과: 차량의 누적 주차 시간이 기본 시간 이하일 경우, 초과 요금 없이 기본 요금만 부과합니다.
  • 초과 요금 계산: 주차 시간이 기본 시간을 초과하면, 초과된 시간을 단위 시간으로 나눈 값을 올림 처리하여 초과 요금을 계산합니다. 이 과정에서, 나누기 연산을 정확하게 처리하기 위해 double 타입을 사용하여 소수점 이하도 유효하게 계산됩니다. 그 후, Math.ceil() 메서드를 사용해 올림 처리하여, 초과 요금이 정확히 반영될 수 있도록 합니다.

󰄉 Complexity

  • ⏳ TC: O(n)
  • 💾 SC: O(n)

이 알고리즘의 시간 복잡도는 O(n)입니다. 주차 기록을 한 번 순회하며 데이터를 처리하고, 최종적으로 주차 요금을 계산하기 때문입니다. 공간 복잡도 역시 O(n)으로, 차량 수에 비례하여 입출차 기록과 주차 시간을 저장하는 데 필요한 메모리를 사용합니다.

  • Algorithm
  • Simulation