주차 요금 계산 (Java, 구현, 프로그래머스)

문제 자체는 아주 쉬운 난이도였지만 해당 문제를 풀면서 String 정렬에 대해 눈에 띌 정도로 차이를 발견하여 작성한다.

 

해당 문제는 마지막에 정답을 리턴할때 String의 오름차순으로 정렬해서 리턴해야 했는데

Map을 항상 정렬 상태로 유지시켜주는 TreeMap 자료구조를 사용하거나

HashMap을 이용하고 마지막에 문제 조건에 따라 정렬을 시행하고 리턴하는 방법이 있었다.

 

TreeMap 이용

 

 

import java.util.*;

class Solution {
    //Map<차량번호, 총주차시간>
    public int[] solution(int[] fees, String[] records) {
        Map<String, Integer> map = new TreeMap<>();
        Map<String, Boolean> isOut = new HashMap<>();
        
        ...
        
        int[] answer = new int[map.size()];
        int i = 0;
        for (String s : map.keySet()) {
            answer[i++] = map.get(s);
        }

        return answer;
    }
}

 

HashMap 후 정렬

 

 

import java.util.*;

class Solution {
    //Map<차량번호, 총주차시간>
    public int[] solution(int[] fees, String[] records) {
        Map<String, Integer> map = new HashMap<>();
        Map<String, Boolean> isOut = new HashMap<>();
		
        ...
        
        int[] answer = new int[map.size()];
        Object[] mapkey = map.keySet().toArray();
		Arrays.sort(mapkey);
        for (int i = 0; i < answer.length; i++) {
            answer[i] = map.get(mapkey[i]);
        }
        return answer;
    }
}

 

눈에 띌 정도로 성능 차이가 존재했다.

테스트를 돌릴 때마다 시간이 달라졌지만 평균적으로 10~30% 가량 차이가 났다.

TreeMap은 레드블랙트리로 구현되어 있어 항상 정렬 상태를 유지해야하므로 IO 성능이 좋지 않을 수 밖에 없다.

반드시 항상 정렬 상태를 유지해야하는 것이 아니라면 HashMap을 통해 구현하고 마지막에 sorting을 진행하는 것이 시간효율적이다.

 

전체 코드

 

import java.util.*;

class Solution {
    //Map<차량번호, 총주차시간>
    public int[] solution(int[] fees, String[] records) {
        Map<String, Integer> map = new HashMap<>();
        Map<String, Boolean> isOut = new HashMap<>();
        
        for (String s : records) {
            String[] record = s.split(" ");
            String hour = record[0].split(":")[0];
            String minute = record[0].split(":")[1];
            
            int time = Integer.parseInt(hour) * 60 + Integer.parseInt(minute);
            String num = record[1];
            String io = record[2];
            
            if (io.equals("IN")) {
                map.put(num, map.getOrDefault(num, 0) - time);
                isOut.put(num, false);
            } else if (io.equals("OUT")) {
                map.put(num, map.getOrDefault(num, 0) + time);
                isOut.put(num, true);
            }
        }
        int end = 23 * 60 + 59;
        for (String s : isOut.keySet()) {
            if (!isOut.get(s)) 
                map.put(s, map.getOrDefault(s, 0) + end);
        }
        for (String s : map.keySet()) {
            if (map.get(s) <= fees[0]) map.put(s, fees[1]);
            else {
                int money = fees[1] + (int)(Math.ceil((double)(map.get(s) - fees[0]) / fees[2])) * fees[3];
                map.put(s, money);
            }
            
        }
        int[] answer = new int[map.size()];
        Object[] mapkey = map.keySet().toArray();
		Arrays.sort(mapkey);
        for (int i = 0; i < answer.length; i++) {
            answer[i] = map.get(mapkey[i]);
        }
        return answer;
    }
}