프로그래머스~숫자 짝꿍(Java)

 

프로그래머스 숫자 짝꿍 - 자바 : https://school.programmers.co.kr/learn/courses/30/lessons/131128?language=java

프로그래머스

문제 설명
두 정수 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"

처음에 이 문제를 보았을 땐, 단순히 X, Y를 배열화 해 이중for문으로 동일한 숫자를 추출, 가장 큰 수를 조합하는 방법을 생각했습니다. 하지만 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000이 조건에서 보듯, 3,000,000이 되는 경우 처리속도가 매우 느려집니다.
좀 더 빠른 처리를 하기 위해 숫자 0~9까지의, 길이 10의 배열을 만들어 그 반복되는 수를 카운트 해 보도록 만들어 보았습니다.

public class day55 {
    public String solution(String X, String Y) {
        String answer = "";
        StringBuilder sb = new StringBuilder();
        int[] arrX = new int[10];
        int[] arrY = new int[10];

        for(String a : X.split("")){
            arrX[Integer.parseInt(a)]++; 
        }

        for(String b : Y.split("")){
            arrY[Integer.parseInt(b)]++; 
        }

        for(int i=9; i>=0; i--){
            if(arrX[i]>0 && arrY[i]>0){
                int tmpInt = Math.min(arrX[i], arrY[i]);
                for(int j=0; j<tmpInt; j++){
                    sb.append(i);
                }
            }
        }

        if (sb.length()>0){
            answer = sb.charAt(0)=='0'? "0": sb.toString();
        } else {
            answer = "-1";
        }

        return answer;
    }
}

소스를 부분적으로 분석 해 봅시다.

        int[] arrX = new int[10];
        int[] arrY = new int[10];

이 코드에서 먼저 카운트를 할 빈 배열을 만듭니다.

숫자	0	1	2	3	4	5	6	7	8	9
arrX	0	0	0	0	0	0	0	0	0	0
arrY	0	0	0	0	0	0	0	0	0	0

        for(String a : X.split("")){
            arrX[Integer.parseInt(a)]++; 
        }

        for(String b : Y.split("")){
            arrY[Integer.parseInt(b)]++; 
        }

상기의 for문으로 카운트를 합니다.
X="5525", Y="1255"로 예를 들면 for문이 실행 된 다음은 아래와 같이 카운트 됩니다.

숫자	0	1	2	3	4	5	6	7	8	9
arrX	0	0	1	0	0	3	0	0	0	0
arrY	0	1	1	0	0	2	0	0	0	0

        for(int i=9; i>=0; i--){
            if(arrX[i]>0 && arrY[i]>0){
                int tmpInt = Math.min(arrX[i], arrY[i]);
                for(int j=0; j<tmpInt; j++){
                    sb.append(i);
                }
            }
        }

arrX, arrY에 카운트된 숫자들만 추출을 해 sb(StringBuilder)에 추가한다.
sb가 큰 수가 될려면 큰 수가 가장 앞자리에 와야하기 때문에 for문을 거꾸로 돌려 가며 공통된 숫자를 추출한다.]
5처럼 공통된 수가 2개 이상인 경우, 겹치는 만큼(적은 카운트)를 반환한다.

        if (sb.length()>0){
            answer = sb.charAt(0)=='0'? "0": sb.toString();
        } else {
            answer = "-1";
        }

마지막으로 겹치는 수가 없을땐 -1을, 0만 여러번 반복하는 경우는 0을 반환하도록 처리를 합니다.