🏆 알고리즘 문제 풀이

📌 문제 정보

• 문제명 : 주차 요금 계산
• 문제 번호 : 92341
• 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/92341
• 난이도 : Lv.2
• 유형 : 구현 / 문자열 / 해시(HashMap)

---

🧐 문제 설명

차량들의 입차(IN) / 출차(OUT) 기록과 요금표가 주어졌을 때
차량 번호 오름차순으로 정렬하여 최종 주차 요금을 계산하는 문제이다.

⏱️ 요금 계산 규칙

항목	의미
기본 시간	기본 요금이 부과되는 시간
기본 요금	기본 시간 안에서 부과되는 요금
단위 시간	초과 시 추가 요금이 붙는 시간 단위
단위 요금	단위 시간마다 추가되는 요금

추가로 다음 규칙을 반드시 고려해야 한다.

✔ 출차 기록이 없는 차량은 23:59 기준으로 자동 출차 처리
✔ 누적 주차 시간을 기준으로 요금 계산
✔ 차량 번호가 낮은 순으로 결과 반환

---

💡 접근 방법

1. 입차 시간 저장용 Map(inTime)
   → 차량 번호 기준으로 가장 최근의 IN 시간을 저장

2. 누적 주차 시간 저장용 Map(totalTime)
   → 차량 번호별 총 이용 시간을 누적

3. 출차 시 시간 계산 후 저장

• OUT이 나오면 (OUT 시간 - IN 시간) 계산하여 totalTime에 누적
• 그리고 해당 차량은 inTime에서 제거

4. 모든 입력 처리 후 아직 IN 상태인 차량 처리

• 출차 기록이 없는 차량은 23:59 기준으로 시간 계산하여 누적

5. 차량 번호 오름차순 정렬 후 요금 계산

• ceil() 연산을 사용하여 단위 시간 초과분 계산

---

📝 문제 설계

변수 / 자료구조	역할	비고
inTime (Map<String, Integer>)	차량 번호 → 마지막 입차 시간 저장	아직 OUT 처리되지 않은 차량만 저장
totalTime (Map<String, Integer>)	차량 번호 → 누적 주차 시간 저장	OUT 시점마다 누적
fees[] (int[])	[기본 시간, 기본 요금, 단위 시간, 단위 요금]	요금 계산 기준

---

⚙️ 시간 복잡도

• 기록 순회 : O(N)
• 차량 번호 정렬 : O(N log N)
  → 전체적으로 충분히 빠름

---

💡 사용 자료구조 / 알고리즘

분류	이유
HashMap	차량별 시간 저장 및 조회가 빠르기 때문
정렬	차량 번호 오름차순 결과 출력
올림(ceil) 계산	단위 요금 반복 부과 처리

---

입력 & 출력 예시

---

🧑‍💻 코드

package Programmers;

import java.util.*;

public class 주차요금계산_92341 {

    public static void main(String[] args) {

        주차요금계산_92341 s = new 주차요금계산_92341();

        // 테스트 입력
        int[] fees = {180, 5000, 10, 600};
        String[] records = {
                "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"
        };

        int[] result = s.solution(fees, records);

        System.out.println(Arrays.toString(result));
    }

    public int[] solution(int[] fees, String[] records) {
        int baseTime = fees[0];
        int baseFee  = fees[1];
        int unitTime = fees[2];
        int unitFee  = fees[3];

        Map<String, Integer> totalTime = new HashMap<>();
        Map<String, Integer> inTime = new HashMap<>();

        for (String record : records) {
            String[] arr = record.split(" ");
            String time = arr[0];
            String car  = arr[1];
            String type = arr[2];

            int minutes = convertToMin(time);

            if (type.equals("IN")) {
                inTime.put(car, minutes);
            } else {
                int diff = minutes - inTime.get(car);
                totalTime.put(car, totalTime.getOrDefault(car, 0) + diff);
                inTime.remove(car);
            }
        }

        int lastTime = convertToMin("23:59");
        for (String car : inTime.keySet()) {
            int diff = lastTime - inTime.get(car);
            totalTime.put(car, totalTime.getOrDefault(car, 0) + diff);
        }

        List<String> carList = new ArrayList<>(totalTime.keySet());
        Collections.sort(carList);

        int[] answer = new int[carList.size()];

        for (int i = 0; i < carList.size(); i++) {
            int time = totalTime.get(carList.get(i));
            answer[i] = calculateFee(time, baseTime, baseFee, unitTime, unitFee);
        }

        return answer;
    }

    private int convertToMin(String time) {
        String[] t = time.split(":");
        return Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
    }

    private int calculateFee(int time, int baseTime, int baseFee, int unitTime, int unitFee) {
        if (time <= baseTime) return baseFee;
        return baseFee + (int) Math.ceil((time - baseTime) / (double) unitTime) * unitFee;
    }
}

---

🔍 코드 해설

1️⃣ 주요 자료구조 및 기본 요금 정보 세팅

변수	의미
totalTime	차 번호별 총 주차 시간 누적
inTime	아직 OUT 처리되지 않은 차량의 입차 시간 저장

---

2️⃣ 입출차 기록 순회 & 시간 계산

for (String record : records) {
    String[] arr = record.split(" ");
    String time = arr[0];
    String car  = arr[1];
    String type = arr[2];

    int minutes = convertToMin(time);

    if (type.equals("IN")) {
        inTime.put(car, minutes);
    } else {
        int diff = minutes - inTime.get(car);
        totalTime.put(car, totalTime.getOrDefault(car, 0) + diff);
        inTime.remove(car);
    }
}

• IN → inTime에 저장
• OUT → 머문 시간 계산 후 totalTime에 누적하고 inTime에서 제거

---

3️⃣ 출차하지 않은 차량 처리 (23:59 강제 OUT)

int lastTime = convertToMin("23:59");
for (String car : inTime.keySet()) {
    int diff = lastTime - inTime.get(car);
    totalTime.put(car, totalTime.getOrDefault(car, 0) + diff);
}

• 아직 OUT 안 한 차량은 → 23:59에 출차한 것으로 계산
  • 예: 18:59 IN → OUT 없음 → 23:59까지 300분 추가

---

4️⃣ 차량 번호 오름차순 정렬 & 요금 계산

List<String> carList = new ArrayList<>(totalTime.keySet());
Collections.sort(carList);

int[] answer = new int[carList.size()];

for (int i = 0; i < carList.size(); i++) {
    int time = totalTime.get(carList.get(i));
    answer[i] = calculateFee(time, baseTime, baseFee, unitTime, unitFee);
}

return answer;

• 차량 번호 오름차순 필수
• 문제 조건에 따라 결과 배열도 정렬된 차량 번호 순서로 요금 삽입.

---

5️⃣ 시간 변환 함수

private int convertToMin(String time) {
    String[] t = time.split(":");
    return Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
}

• "HH:MM" → 분 단위 정수로 변환

---

6️⃣ 요금 계산 함수

private int calculateFee(int time, int baseTime, int baseFee, int unitTime, int unitFee) {
    if (time <= baseTime) return baseFee;
    return baseFee + (int) Math.ceil((time - baseTime) / (double) unitTime) * unitFee;
}

• 요금 계산 공식

기본시간 이하 → 기본요금
초과시간 발생 → ceil(초과시간 / 단위시간) * 단위요금 + 기본요금