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

문제

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

프로그래머스

 

코드

import java.util.*;
class Solution {
    public int[] solution(int[] fees, String[] records) {
        Map<String, Integer> parkIn = new HashMap<>();
        Map<String, Integer> parkingTime = new HashMap<>();
        
        for(int i = 0; i < records.length; i++) {
            String[] tmp = records[i].split(" "); // 0 - time, 1 - number, 2 - in out
            int time = getTime(tmp[0]);
            
            if(tmp[2].equals("IN")) {
                parkIn.put(tmp[1], time);
            } else {
                parkingTime.put(tmp[1], parkingTime.getOrDefault(tmp[1], 0) + (time - parkIn.get(tmp[1])));
                parkIn.remove(tmp[1]);
            }
        }
        
        int endTime = getTime("23:59");
        for(String key : parkIn.keySet()) {
            parkingTime.put(key, parkingTime.getOrDefault(key, 0) + (endTime - parkIn.get(key)));
        }
        
        List<String> carNumbers = new ArrayList<>(parkingTime.keySet());
        Collections.sort(carNumbers); // 차량 번호로 최종 정렬
        
        int[] answer = new int[carNumbers.size()];
        int idx = 0;
        
        for(String car : carNumbers) {
            int time = parkingTime.get(car);
            if(time <= fees[0]) {
                answer[idx++] = fees[1];
            } else {
                answer[idx++] = fees[1] + (int)Math.ceil((double)(time - fees[0]) / fees[2]) * fees[3];
            }
        }
        
        return answer;
    }
    
    int getTime(String time) {
        return Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3, 5));
    }
}

 

접근 방법

- 차랑변호로 records를 정렬한다음에 treemap에 넣어주는 방식으로 풀었음.

Arrays.sort(records, Comparator.comparingInt(r -> Integer.parseInt(r.split(" ")[1])));

- 어차피 정렬이 되어있는데 treemap을 쓸 이유가 없다! -> hashmap으로 변경

- 처음에 정렬하는 것에서 split을 하는게 낭비다? 싶어서 제거 후 나중에 parkingTime을 이용해서 정렬해줌

 

시간 복잡도 비교

M - records의 길이 / N - 차량번호의 개수

1.

처음에 Arrays.sort로 정렬하는거 -> O(M log M)

treemap에 데이터 삽입 삭제 -> O(M log N)

마지막 남은 것들 처리 -> O(N log N)

parkingTime 순회하며 요금 계산 -> O(N)

=> O(M log M + M log N + N log N)

 

hashmap으로 변경

2.

map 삽입 삭제 -> O(M)

차량 번호로 정렬 -> O(N log N)

마지막 남은 것들 처리 -> O(N)

=> O(M + N log N)

 

records의 최대 길이가 1000이기 때문에 treemap을 사용해도 정답이 맞긴하다.

하지만 hasmap을 쓰는게 더 빨라지는 것은 사실이기 때문에 항상 정렬을 어디서 해주는지 깊게 고민해볼 필요가 있는듯하다.