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

문제

숫자 짝꿍
문제 설명
두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.

예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.

제한사항
3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
X, Y는 0으로 시작하지 않습니다.
X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.
입출력 예
X Y result
"100" "2345" "-1"
"100" "203045" "0"
"100" "123450" "10"
"12321" "42531" "321"
"5525" "1255" "552"
입출력 예 설명
입출력 예 #1

X, Y의 짝꿍은 존재하지 않습니다. 따라서 "-1"을 return합니다.
입출력 예 #2

X, Y의 공통된 숫자는 0으로만 구성되어 있기 때문에, 두 수의 짝꿍은 정수 0입니다. 따라서 "0"을 return합니다.
입출력 예 #3

X, Y의 짝꿍은 10이므로, "10"을 return합니다.
입출력 예 #4

X, Y의 짝꿍은 321입니다. 따라서 "321"을 return합니다.
입출력 예 #5

지문에 설명된 예시와 같습니다.

코드1 (73.7%)

import java.util.*;
class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        HashMap<Character, Integer> xmap = new HashMap<>();
        HashMap<Character, Integer> ymap = new HashMap<>();
        ArrayList<Character> list = new ArrayList<>();
        for(int i=0; i<X.length(); i++){
            xmap.put(X.charAt(i),xmap.getOrDefault(X.charAt(i),0)+1);
        }
         for(int i=0; i<Y.length(); i++){
            ymap.put(Y.charAt(i),ymap.getOrDefault(Y.charAt(i),0)+1);
        }
        int n = 0;
        Character common = 0;
        for(Character keys : xmap.keySet()){
            if(ymap.containsKey(keys)){
                common = keys;
                if(xmap.get(keys)>=ymap.get(keys)){
                    n = ymap.get(keys);
                }
                else if (xmap.get(keys)<ymap.get(keys)){
                    n = xmap.get(keys);
                }
                for(int j=1; j<n+1; j++){
                    list.add(common);
                }
            }
            else{
                continue;
            }
        }
        
        Collections.sort(list, Collections.reverseOrder());
        
        for(int i=0; i<list.size(); i++){
            answer += list.get(i)+"";
        }
        if(list.size()==0){
            return "-1";
        }
        if(list.get(0)=='0'){
            return "0";
        }
        return answer;
    }
}

코드2 (100%)

import java.util.*;
class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        HashMap<Character, Integer> xmap = new HashMap<>();
        HashMap<Character, Integer> ymap = new HashMap<>();
        ArrayList<Character> list = new ArrayList<>();
        for(int i=0; i<X.length(); i++){
            xmap.put(X.charAt(i),xmap.getOrDefault(X.charAt(i),0)+1);
        }
         for(int i=0; i<Y.length(); i++){
            ymap.put(Y.charAt(i),ymap.getOrDefault(Y.charAt(i),0)+1);
        }
        int n = 0;
        Character common = 0;
        for(Character keys : xmap.keySet()){
            if(ymap.containsKey(keys)){
                common = keys;
                if(xmap.get(keys)>=ymap.get(keys)){
                    n = ymap.get(keys);
                }
                else if (xmap.get(keys)<ymap.get(keys)){
                    n = xmap.get(keys);
                }
                for(int j=1; j<n+1; j++){
                    list.add(common);
                }
            }
            else{
                continue;
            }
        }
        
        Collections.sort(list, Collections.reverseOrder());
        if(list.size()==0){
            return "-1";
        }
        if(list.get(0)=='0'){
            return "0";
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<list.size(); i++){
            sb = sb.append(list.get(i));
        }
        answer = sb.toString();
        return answer;
    }
}

풀이

X와 Y각각 숫자와 빈도수를 담은 MAP을 생성했다. 이후
X와 Y에서 공통적으로 발견된 문자를 동일한 빈도로 찾아서, 그 문자들을 내림차순으로 정렬하고 문자열로 반환한다. 두 문자열에서 공통으로 발견된 문자의 수가 더 적은 것을 기준으로 문자를 추가했다.

코드1에서 시간초과로 인해 실패한 케이스들이 있었다.

answer += list.get(i)+"";

이렇게 문자열로 이어 붙히는 부분이 문제라고 생각하여, 코드 2에서

        for(int i=0; i<list.size(); i++){
            sb = sb.append(list.get(i));
        }
        answer = sb.toString();

위 처럼 StringBuilder로 개선해주었더니 통과할 수 있었다.
Stirng을 이어 붙혀야할 때는 무조건 StringBuilder로 바꿔주자!

그리고....
-숫자로 이루어진 Character 리스트를 정렬하는 경우에도 ASCII 값에 따라 정렬이 수행된다. '0'부터 '9'까지의 ASCII 값은 각각 48부터 57까지이다. 따라서 '0'은 '9'보다 작다고 판단되고 이런 경우, 숫자의 크기가 아닌 ASCII 값에 따라 정렬이 수행됩니다.
(위처럼 해도 상관 없지만 꼭 숫자로 하고 싶으면
Character.getNumericValue() 메소드를 이용하여 Character를 숫자로 변환하여 추가한다.)