프로그래머스 - 숫자 짝꿍

풀이.

이 문제는 두 가지 방법으로 풀어 볼 수 있다.
하나는 Hash를 이용한 방법과 하나는 계수정렬 방법 두 개다 풀어보자.

1. Hash

문자열 X와 문자열 Y를 담을 HashMap을 각 각 만들어
getOrDefault 메서드를 이용해 최빈값을 구한다.
우리가 원하는 건 X, Y에서 나오는 공통된 수 중 가장 큰 정수
'9' 부터 '0'까지 순회화면서 각 요소가 두 해시맵에 키가 있을 때
밸류가 작은 값을 스트링빌더에 추가해주고 문자열로 변환한 후
비었을 때 = 공통된 수가 없음 = -1 리턴
0이 여러개 일 때 = 0을 "' 다 바꾸고 빈 문자열이면 = 0 리턴
둘다 해당되지 않으면 answer 리턴

import java.util.HashMap;

class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        HashMap<Character, Integer> mapX = new HashMap<>();
        HashMap<Character, Integer> mapY = new HashMap<>();
        
        for (Character x : X.toCharArray()) {
            mapX.put(x, mapX.getOrDefault(x, 0) + 1);
        }
        for (Character y : Y.toCharArray()) {
            mapY.put(y, mapY.getOrDefault(y, 0) + 1);
        }
        
        StringBuilder sb = new StringBuilder();
        for (char ch = '9'; ch >= '0'; ch--) {
            if (mapX.containsKey(ch) && mapY.containsKey(ch)) {
                int min = Math.min(mapX.get(ch), mapY.get(ch));
                for (int i = 0; i < min; i++) {
                    sb.append(ch);
                }
            }
        }
        
        answer = sb.toString();
        if (answer.isEmpty()) {
            return "-1";
        }
        if (answer.replaceAll("0", "").isEmpty()) {
            return "0";
        }
        
        return answer;
    }
}

 

2. 계수 정렬 이용하기

계수 정렬은 정렬되지 않은 배열에서 범위가 작을 때 그 범위내 값이 몇번 나오는지 세는(계수)하는 알고리즘이다.
계수 정렬은 정수나 정수로 변환 가능한 객체들에 대해 사용할 수 있으며, 각 항목의 빈도를 세어 사용하는 정렬 알고리즘이다.

이 문제에서는 0 ~ 9 까지 나올 수 있는 숫자 범위가 작기 때문에 적용 가능하다.

먼저 X와 Y 문자열에 대한 int[10] 배열을 각 각 만들고 
X, Y 문자열을 순회하면서 각 자리에 맞는 수가 나오면 index에 ++ 해준다.

그다음은 위와 반복문 변수 선언 외에는 비슷하기 때문에 설명은 생략...

class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        int[] xCnt = new int[10];
        int[] yCnt = new int[10];
        
        for (char ch : X.toCharArray()) {
            xCnt[ch - '0']++;
        }
        
        for (char ch : Y.toCharArray()) {
            yCnt[ch - '0']++;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 9; i >= 0; i--) {
            int min = Math.min(xCnt[i], yCnt[i]);
            for (int j = 0; j < min; j++) {
                sb.append(i);
            }
        }
        
        answer = sb.toString();
        if (answer.isEmpty()) {
            return "-1";
        }
        if (answer.replaceAll("0", "").isEmpty()) {
            return "0";
        }
                
        return answer;
    }
}