📌 문제

Lv1. 숫자 짝꿍

두 정수 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의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

✏️ 입출력

1. 입출력 예 #1 : X, Y의 짝꿍은 존재하지 않습니다. 따라서 "-1"을 return합니다.
   
   
2. 입출력 예 #2 : X, Y의 공통된 숫자는 0으로만 구성되어 있기 때문에, 두 수의 짝꿍은 정수 0입니다. 따라서 "0"을 return합니다.
   
   
3. 입출력 예 #3 : X, Y의 짝꿍은 10이므로, "10"을 return합니다.
   
   
4. 입출력 예 #4 : X, Y의 짝꿍은 321입니다. 따라서 "321"을 return합니다.
   
   
5. 입출력 예 #5 :지문에 설명된 예시와 같습니다.

💡 코드

⌛ 시간 초과 : 공통으로 나타나는 정수를 저장할 리스트 pair을 선언하고, contains()를 통해 X의 요소가 Y에 있는지 판단한 후, 포함되어 있다면 pair에 해당 요소를 추가한다. 이 때, Y에서 해당 요소의 짝을 지어줬으므로 다음에 같은 요소가 또 있을 때 사용되지 않게 replaceFrist("")를 통해 제거해줬다. (replace("") 사용 시, 중복 되는 모든 요소를 대체하므로 하나만 대체할 수 있게 replaceFirst("")를 사용했다.)

리스트의 요소들로 가장 큰 정수를 만들어야 하므로, Collection.reverseOrder()를 통해 요소들을 내림차순 정렬한 후, 요소들을 순서대로 꺼내 문자열로 만들어서 리턴한다. 이 때, 리스트에 요소가 하나도 없으면 "-1"을, 완성된 문자열의 첫 자리가 0이면 해당 문자열을 0으로만 구성되어있다는 뜻이므로 "0"을 리턴해야 한다.

해당 코드를 수행하니 몇 개의 케이스에서 시간 초과가 발생하였고,, 성공한 케이스들의 실행 시간도 꽤나 길었다,, 아무래도 문자열의 자릿수가 최대 3백만이다 보니 문자열 연산에서 시간을 많이 잡아먹었나? 싶어서 StringBuilder도 사용해봤는데 여전히 같은 케이스들에서 시간 초과가 발생하였고,, 아무래도 contains(), collections.sort() 등 다양한 곳이 원인인 것 같다는 생각이 들었다,,

import java.util.*;
class Solution {
    public String solution(String X, String Y) {
        
        List<Integer> pair = new ArrayList<>();
        
        for(int i=0;i<X.length();i++) {
            String x = X.charAt(i) + "";
        
            if(Y.contains(x)) {
                pair.add(Integer.parseInt(x));
                Y = Y.replaceFirst(x, "");
            }
        }
        
        Collections.sort(pair, Collections.reverseOrder());
        
        if(pair.size() == 0) return "-1";
        
        /*
        else {
            String answer = "";
            
            for(int i : pair) {
                answer += i+"";
            }
            
            if(answer.charAt(0) == '0') return "0";
            else return answer;
        }
        */
       
        else {
            StringBuilder sb = new StringBuilder();
            
            for(int i : pair) {
                sb.append(i);
            }
            
            if(sb.charAt(0) == '0') return "0";
            else return sb.toString();
        }
        

    }
}

✅ 이전 코드에서 시간을 잡아먹을법한 contains(), replaceFirst(), Collections.sort()를 최대한 빼는 쪽으로 문제를 풀어보려고 노력했다..

일단 숫자의 범위가 0~9 이므로 문자열 X, Y에 포함된 각 숫자의 개수를 카운트하는 크기가 10인 배열 x, y를 선언한 후, 숫자에 해당하는 인덱스의 값을 증가시켜줬다.

이후, 가장 큰 정수를 만들어야 하므로 9~0 순으로 반복문을 돌면서 x, y 모두 해당 숫자를 하나 이상 가지고 있을 때만 정답 문자열에 추가해줬다. 이때, 문자열 연산은 시간을 많이 걸리므로 StringBuilder의 append()를 사용하였다. 최종 sb의 길이가 0이면 짝꿍 숫자가 없다는 뜻이므로 "-1", 첫 글자가 0이라면 0으로만 구성된 문자열이므로 "0", 위 두 케이스에 포함되지 않는 나머지는 sb.toString()을 리턴한다.

확실히 위 코드에서 사용했던 정렬, String 메서드를 사용하지 않으니 실행 시간이 엄청나게 감소하였다!

class Solution {
    public String solution(String X, String Y) {

        int[] x = new int[10];
        int[] y = new int[10];
        
        for(int i=0;i<X.length();i++) {
            x[X.charAt(i) - 48]++;
        }
        
        for(int i=0;i<Y.length();i++) {
            y[Y.charAt(i) - 48]++;
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=9;i>=0;i--) {
            while(x[i] >= 1 && y[i] >= 1) {
                x[i]--;
                y[i]--;
                
                sb.append(i);
            }
        }
        
        if(sb.length() == 0) return "-1";
        else if(sb.charAt(0) == '0') return "0";
        return sb.toString();
    }
}