문제

Programmers - 주차 요금 계산

요약

차량의 입·출차 기록이 주어질 때, 주차장의 정해진 기본요금, 추가요금에 맞게 각 차량별 주차요금을 계산해야한다.

단, 입차 후 출차 기록이 없는 차량은 23:59에 나간 것으로 간주.
추가 요금 발생 시간이 나누어 떨어지지 않는 경우, 올림으로 시간을 반영해 추가요금 청구.
최종 결과는 차량 번호의 오름차순대로 누적 요금을 출력할 것.

접근

이 문제를 처음 봤을 때, 문제의 길이가 길어서 이해할게 많고, 알고리즘까지 생각하기 어려울 것이라 생각했다.
근데, 긴 문제의 특징은 요구하는 사항에 맞게 구현만 올바르게 하면 되는 것이었다.
문제의 요구사항을 파악하고 이를 코드로 적절히 옮기기만한다면 문제가 해결될 것이라 생각했다.
여기서 핵심은 차량을 관리하는 자료구조를 어떤 것을 쓸 것이냐였다.

알고리즘

이번 문제는 알고리즘이라기보단, 자료구조를 선택하는게 키포인트였다.

먼저 차량의 입출차 정보를 기록하기 위해선 Map 자료구조로 key, value로 차량의 입차정보를 관리했다.
차량이 출차되는 순간 해당 차량의 정보를 key로 조회해서 출차시간과 입차시간을 계산한다.
그 값을 차량의 누적 주차시간을 저장할 또다른 Map에 저장한다.
이때, 해당 Map은 TreeMap을 사용한다.

• TreeMap은 key 값을 자동으로 오름차순 정렬하는 특징이 있다. 이를 활용해 문제의 조건인 오름차순 정렬을 해결한다.
  최종적으로 TreeMap에 저장된 차량 번호 순서대로 누적 시간을 가져와서 이를 요금 기준에 맞게 계산하면 해결된다.

제출 코드

import java.util.HashMap;
import java.util.TreeMap;
import java.util.Set;

class Solution {
    static int giTime;
    static int giFee;
    static int danTime;
    static int danFee;
    
    public int[] solution(int[] fees, String[] records) {
        
        giTime = fees[0];
        giFee = fees[1];
        danTime = fees[2];
        danFee = fees[3];
        // 입출차 관리 맵
        HashMap<Integer, String> map = new HashMap<>();
        // 차량별 누적 요금 관리
        TreeMap<Integer, Integer> carTime = new TreeMap<>();
        
        for (String r : records) {
            String[] record = r.split(" ");
            String time = record[0]; // 시각
            int car = Integer.parseInt(record[1]); // 차량 번호
            String ny = record[2]; // 내역
            // 입차
            if (ny.equals("IN")) {
                map.put(car, time);
            }
            // 출차
            else {
                int totalTime = 0;
                // 입차했던 시간 가져옴. 동시에 해당 차량 삭제
                String icTime = map.remove(car);
                String[] ic = icTime.split(":"); // 입차시간
                String[] cc = record[0].split(":"); // 출차시간
                int min = Integer.parseInt(cc[1]) - Integer.parseInt(ic[1]);
                int hour = Integer.parseInt(cc[0]) - Integer.parseInt(ic[0]);
                if (min < 0) {
                    min = 60 + min;
                    hour -= 1;
                }
                // 누적 주차 시간
                totalTime = hour * 60 + min;
                // 차에 시간을 누적함 (차량이 처음 누적될 때 "getOrDefault"로 에러 방지)
                carTime.put(car, carTime.getOrDefault(car, 0) + totalTime);
            }
        }
                
        // 입차 후 출차하지 않은 차량 관리
        for (int carNum : map.keySet()) {
            int totalTime = 0;
            String icTime = map.get(carNum);
            String[] ic = icTime.split(":"); // 입차시간
            int min = 59 - Integer.parseInt(ic[1]);
            int hour = 23 - Integer.parseInt(ic[0]);
            // 누적 주차 시간
            totalTime = hour * 60 + min;
            // 차량별 누적 요금 관리
            carTime.put(carNum, carTime.getOrDefault(carNum, 0) + totalTime);
        }
        
        int[] answer = new int[carTime.size()];
        int idx = 0;
        for (int time : carTime.values()) {
            answer[idx] = payFee(time);
            idx++;
        }
        
        return answer;
    }
    
    // 요금 계산
    public static int payFee (int time) {
        int totalFee = giFee;
        time -= giTime;
        if (time <= 0) return totalFee;
        
        if (time % danTime == 0) {
            totalFee += time/danTime*danFee;
        }
        else {
            totalFee += (time/danTime+1)*danFee;
        }
        return totalFee;
    }
}

어려웠던 점

TreeMap이라는걸 이 문제를 풀면서 처음 알았다. 오름차순으로 차량 정보를 조회해오는 방법을 생각해봤을 때, 처음에 1차원 배열을 9999까지 만들고 할까 생각했는데, 이는 메모리 낭비라는 생각이 들어 List로 관리할까하다가 이는 코드의 복잡성이 올라가 어떻게 해결하지 아이디어가 떠오르지 않았다.

이를 Gemini에게 물어보니 TreeMap이라는 자료구조를 알려줘서 이를 활용했다.
활용할 때, 핵심은 Map에 값을 집어넣을 때, 키 값이 없다면, getOrDefault로 누적 시간의 값을 0으로 지정해서 누적 시간 값을 value에 집어 넣는 것이었다.

그리고 시간을 올림해서 처리하는 것도 처음엔 if else문으로 처리했는데, 이를 더 간단히 해결하려고 Math.ceil을 사용했다.

근데, 그냥 ceil을 사용하니 올림이 적용이 안됐다. 이는 Java의 '/'연산은 몫만 남기므로 ceil을 한다고 한들 그냥 내림 계산이 되어버린다.

이를 해결하려면, 연산되는 값을 double로 지정해서 소숫점 값이 나오도록 해야했다.
이 부분을 놓쳐서 디버깅하는데 시간을 오래 썼다. 어찌보면 당연한건데, 아직 많이 공부해야하나보다..
아래는 최종 제출한 코드를 조금 더 개선시킨 코드이다.

• Map의 자료형 변경 및 일부 계산식 단순화 (시간 계산, 요금 계산)

...
class Solution {
	...
    public int[] solution(int[] fees, String[] records) {
		...
        // 입출차 관리 맵 (차 번호, 입차 시간)
        HashMap<String, Integer> map = new HashMap<>();
        // 차량별 누적 시간 관리 (차 번호, 누적 주차 시간)
        TreeMap<String, Integer> carTime = new TreeMap<>();
        
        for (String r : records) {
            ...
            // 절대 분 단위 환산
            String[] hhmm = time.split(":");
            int currentMin = Integer.parseInt(hhmm[0]) * 60 + Integer.parseInt(hhmm[1]); 
            // 입차
            if (ny.equals("IN")) {
                map.put(car, currentMin);
            }
            // 출차
            else {
                // 입차했던 시간 가져옴. 동시에 해당 차량 삭제
                int icTime = map.remove(car);
                
                // 누적 주차 시간
                int totalTime = currentMin - icTime;
                // 차에 시간을 누적함 (차량이 처음 누적될 때 "getOrDefault"로 에러 방지)
                carTime.put(car, carTime.getOrDefault(car, 0) + totalTime);
            }
        }
                
        // 입차 후 출차하지 않은 차량 관리
        for (String carNum : map.keySet()) {
            int icTime = map.get(carNum);
            // 누적 주차 시간
            int totalTime = 23*60+59 - icTime;
            // 차량별 누적 요금 관리
            carTime.put(carNum, carTime.getOrDefault(carNum, 0) + totalTime);
        } 
        ...
        return answer;
    }
    
    // 요금 계산
    public static int payFee (int time) {
        int totalFee = giFee;
        time -= giTime;
        if (time <= 0) return totalFee;
        
        // double로 해야 소수점이 생겨서 올림이 가능
        totalFee += Math.ceil((double)time/danTime)*danFee;
        
        return totalFee;
    }
}