[내일배움캠프] 알고리즘 Daily Routine 63. 숫자 짝꿍

안녕하세요.
63회차 과제 숫자 짝꿍입니다.

---

문제

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 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차 시도(실패)

단순한 방법으로 풀어보았습니다.
X를 split하여 for 반복문으로 Y에 strX가 들어있는지 확인하여 들어있는경우 Y에서 해당 숫자를 제외하는 방법을 사용했습니다.
이 방법을 사용할 경우 간단한 숫자는 무리없이 계산할 수 있었지만 큰 수가 나오는 계산의 경우 런타임 에러가 발생하거나 시간을 초과하는 경우가 생겼습니다.

import java.util.*;
class Solution {
    public String solution(String X, String Y) {
        String[] strX = X.split("");
        String answer = "";
        List<String> num = new ArrayList<>();    
        for (String a : strX){
            if(Y.contains(a)){
                Y = Y.replaceFirst(a,"");
                num.add(a);
            }
        }
        if(num.isEmpty()){
            answer = "-1";
        } else {
            num.sort((a, b) -> b.compareTo(a));
            for (String c : num) {
                answer += c;
            }
            if(Integer.parseInt(answer) == 0){
                answer = "0";
            }
        }
        return answer;
    }
}

 

2차 시도(성공)

방법을 바꿔보았습니다.
X와 Y에 포함된 0 ~ 9까지의 숫자의 갯수를 세고 큰 숫자부터 갯수만큼 출력하는 방법을 사용했습니다.

import java.util.*;
class Solution {
    public String solution(String X, String Y) {
        int[] countX = new int[10];
        int[] countY = new int[10];

        for(int i=0; i<X.length(); i++){
            char charX = X.charAt(i);
            countX[charX - '0']++;
        }
        for(int i=0; i<Y.length(); i++){
            char charY = Y.charAt(i);
            countY[charY - '0']++;
        }

        StringBuilder answer = new StringBuilder();
        for(int i=9; i>=0; i--){
            int countNum = Math.min(countX[i], countY[i]);
            for(int j=0; j<countNum; j++){
                answer.append(i);
            }
        }

        if(answer.length() ==0){
            return "-1";
        }

        if(answer.charAt(0)=='0'){
            return "0";
        }

        return answer.toString();
    }
}

---

Learned

int[char - '0']
countX[charX - '0']++;

특정 숫자가 몇 번 나오는지 확인하기 위한 부분입니다.
char - '0' 는 char 형식을 int 형식의 숫자로 변환해줍니다.
사용된 수식으로 풀어본다면 charX가 '5'일 경우 char형식의 '5'를 int형식의 5로 변환하여 count[5]++; 가 됩니다.
즉, count[5]의 값을 +1합니다.

---

Math.min(a, b)
Math.min(countX[i], countY[i])

a와 b중 더 작은 값을 반환하는 메서드입니다.
사용된 수식으로 풀어본다면 i위치에 해당하는 숫자의 갯수 중 작은 숫자의 갯수를 반환합니다.
즉, X에서 5가 3개 존재하고 Y에서 5가 2개 존재한다면 i가 5일 때 countX는 3이고 countY는 2이니 Math.min은 더 작은 값인 2를 반환하여 X와 Y의 5의 갯수 중 매칭되는 갯수만 반환합니다.

---

저처럼 개발을 처음 접하시는 분들에게 이 글이 조금이나마 도움이 되길 바랍니다.