[프로그래머스|JAVA] 주차 요금 계산 | TreeMap과 Map.merge 활용 🚗 | 시간 계산 아이디어 & 코드 분석 📚

정말 오랜만에  왔습니다.. 반성합니다..

 

[문제 링크]

프로그래머스

 

[문제]

 

---

 

📍 [코드]

// 맵 사용 (번호, 시간)
// 시간 * 60 후 계산
import java.util.*;

class Solution {
    
    int pullTime = (23 * 60) + 59; // 23시 59분
    
    public int[] solution(int[] fees, String[] records) {
        Map<String, Integer> chargeMap = new TreeMap<>(); // 차량 번호 순 정렬 가능
        
        for(String r : records) {
            String[] parts = r.split(" ");
            String car = parts[1], type = parts[2];
            int time = pullTime - timeToMin(parts[0]);
            
            chargeMap.merge(car, type.equals("IN") ? time : -time, Integer::sum);
        }
        
        return chargeMap.values()
                .stream()
                .mapToInt(time -> calculateFee(time, fees))
                .toArray();
    }
    
    // 요금 계산
    public int calculateFee (int time, int[] fees){
        if (time <= fees[0]) return fees[1];
        return fees[1] + (int) Math.ceil((time - fees[0]) / (double) fees[2]) * fees[3];
    }
    
    // 시간 변환
    public int timeToMin (String time){
        String[] parts = time.split(":");
        int hour = Integer.parseInt(parts[0]);
        int min = Integer.parseInt(parts[1]);
        return (hour * 60) + min;
    }
}

 

 

💡 접근법

이번 문제는 차량별 누적 주차 시간을 구하고, 그 시간에 따라 요금을 계산하는 것이 핵심입니다.

특히, 출차 기록이 없는 경우 23:59에 출차한 것으로 간주해야 하고, 최종 결과는 차량 번호 오름차순으로 정렬해야 합니다.

• 자료구조 선택: 차량 번호(String)를 Key로, 누적 주차 시간(Integer)을 Value로 저장할 `Map`이 필요합니다. 최종 결과를 차량 번호 순으로 정렬해야 하므로, Key가 자동으로 정렬되는 `TreeMap`을 사용했습니다.
• 시간 계산 아이디어: 입/출차 기록을 순회하며 시간을 계산하는 것이 번거로울 수 있습니다. 대신 "23:59까지 남은 시간"을 활용하는 아이디어를 적용했습니다.
  • `pullTime = (23 * 60) + 59` 로 하루의 총 분(1439분)을 미리 계산해 둡니다.
  • `timeToMin` 함수로 "HH:MM" 형식의 시간을 분으로 변환합니다.
  • 각 기록의 시간 t에 대해 `pullTime - t`는 "해당 시각부터 23:59까지 남은 시간"이 됩니다.
• `Map.merge` 활용: TreeMap에 누적 시간을 계산하는 과정에서 merge 메서드를 사용했습니다.
  • 입차 (IN): 해당 차량 번호에 +(pullTime - 입차시간)을 더합니다.
  • 출차 (OUT): 해당 차량 번호에 -(pullTime - 출차시간)을 더합니다. (즉, 남은 시간을 빼줌)
  • 결과: 특정 차량에 대해 모든 기록을 처리하고 나면, `(pullTime - 입차1) - (pullTime - 출차1) + (pullTime - 입차2) - (pullTime - 출차2) + ...` 와 같이 계산됩니다. pullTime 항은 서로 상쇄되어 결국 `(출차1 - 입차1) + (출차2 - 입차2) + ... `즉, 총 주차 시간(분)만 남게 됩니다.
  • 출차 기록 없는 경우: 마지막 입차 기록에 대한 +(pullTime - 입차시간)만 남아, 자동으로 23:59 출차로 간주하여 계산됩니다.
• 최종 요금 계산: TreeMap의 values() (누적 주차 시간 목록)를 스트림으로 변환하여 각 시간마다 `calculateFee` 메서드를 적용, 최종 요금 배열을 생성합니다.
  • `calculateFee`에서는 기본 시간 초과 시 추가 요금을 계산할 때, 단위 시간으로 나누어 올림(Math.ceil) 처리하는 부분에 주의해야 합니다.

---

✅ 핵심 포인트

• `TreeMap` 활용: Key(차량 번호) 기준 자동 정렬 기능을 활용하여 문제의 요구사항(차량 번호 오름차순 출력)을 쉽게 만족시킬 수 있습니다.
• `Map.merge` 활용: map.put(key, map.getOrDefault(key, 0) + value) 와 같은 코드를 map.merge(key, value, Integer::sum) 으로 간결하게 표현하여 가독성을 높일 수 있습니다.
• 시간 계산 아이디어: "23:59까지 남은 시간"을 이용하여 입/출차 시간을 누적 계산하면, 출차 기록이 없는 경우까지 자연스럽게 처리할 수 있습니다.

---

 

⏳ 시간 복잡도: O(N log K)

• `N`: 주차 기록 records의 개수
• `K`: 고유한 차량의 수
• records 배열 한 번 순회 `(O(N))`
• 각 기록마다 TreeMap에 merge 연산을 수행하는데, 이는 평균적으로 `O(log K)`의 시간이 걸림
• 최종적으로 TreeMap의 값들을 스트림으로 처리하는 데 `O(K)`걸림
• 따라서 전체 시간 복잡도 : `O(N log K)`

---

 

💬 마무리

처음 문제를 봤을 때 입/출차 시간을 어떻게 짝지어 관리할지 고민이 많았습니다. 하지만 질문하기를 통해 "23:59까지 남은 시간"을 활용하는 아이디어를 얻었고, Map.merge를 적용하니 코드가 훨씬 간결하고 효율적으로 작성될 수 있었습니다. 특히 출차 기록이 없는 경우를 별도로 처리할 필요가 없다는 점이 인상 깊었습니다.
TreeMap의 자동 정렬 기능과 Map.merge의 편리함을 제대로 경험할 수 있었고, 다시 열심히 공부를 해야겠다고 다짐하는 계기가 되었습니다.