HashMap을 이용한 빈도수 측정(숫자 짝궁)

프로그래머스 문제를 풀고 다른 사람의 풀이를 보면서 HashMap의 사용을 머리속에 남겨놓기 위해 글을 씁니다.

 

프로그래머스 해당 문제는 숫자 짝꿍입니다.

 

제가 풀이했던 방법은

public String solution(String X, String Y) {
        String answer = "";

        ArrayList<Integer> xArray = new ArrayList<>();
        ArrayList<Integer> yArray = new ArrayList<>();

        String[] xStringArray = X.split("");
        String[] yStringArray = Y.split("");

        ArrayList<Integer> arrayList = new ArrayList<>();

        for (String s : xStringArray) {
            xArray.add(Integer.parseInt(s));
        }

        for (String s : yStringArray) {
            yArray.add(Integer.parseInt(s));
        }

        for (Integer x : xArray) {
            if (yArray.remove(x)) {
                arrayList.add(x);
            }
        }

        if (arrayList.size() == 0) {
            return "-1";
        }

        arrayList.sort(Collections.reverseOrder());

        StringBuilder sb = new StringBuilder();
        for (int num : arrayList) {
            sb.append(num);
        }

        String result = sb.toString();
        if (result.startsWith("0")) {
            return "0";
        }

        answer = result;

        return answer;
    }

이런 방식으로, return 값은 맞출 수 있으나 시간복잡도를 전혀 고려하지 않아서 시간 초과가 된 풀이입니다.

 

 

해결 방법이 떠오르지 않아 다른 사람들의 풀이를 봤는데 HashMap을 이용해 Key, value로 빈도수를 측정한 것이 있더라구요.

public String solution(String X, String Y) {
        Map<String, Integer> xMap = new HashMap<>();
        Map<String, Integer> yMap = new HashMap<>();
        
        List<String> list = new ArrayList<>();
        
        for(String key: X.split("")) {
            xMap.put(key, xMap.getOrDefault(key, 0)+1);
        }
        
        for(String key: Y.split("")) {
            yMap.put(key, yMap.getOrDefault(key, 0)+1);
        }
        
        for(String key: xMap.keySet()) {
            if(!yMap.containsKey(key)) continue;
            
            int length = Math.min(xMap.get(key), yMap.get(key));
            for(int i = 0; i < length; i++) {
                list.add(key);
            }
        }
        
        String result = list.stream()
            .sorted(Collections.reverseOrder())
            .collect(Collectors.joining());
        
        if(result.isEmpty()) return "-1";
        if(result.replaceAll("0", "").isEmpty()) return "0";
        return result;
    }

key값으로 해당 숫자를, value로 빈도수를 기록하고 X,  Y의 같은 키 값들 중 작은 빈도수를 가지고 와서 그 빈도수 만큼 새로운 list에 추가해 정렬한겁니다.

 

이때까지 풀이를 하면서 list로만 생각을 해봤지 HashMap을 사용한 것은 생각해보지 못했네요.. 다음 문제를 풀어볼 떄는 HashMap을 사용한 방법도 고려를 해봐야겠습니다.. 시간 복잡도 관련한 부분은 나중에 따로 정리를 해봐야겠네요!