프로그래머스 숫자 짝꿍

• 숫자 짝꿍

문제 설명

 

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

---

입출력 예XYresult

"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. 두 정수 x,y를 각각 배열에 담아준다. 

2. 같은 값을 비교하여 구해준다. 

3.  그 후, 짝궁 존재하지않으면 -1, 존재하지만 0이면 0 아니면 가장 큰 짝궁을 구해준다.

4. 가장 큰 짝궁을 구해주기 위해서는 가장 큰 수

 

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        char []xArr = new char[X.length()];
        char []yArr = new char[Y.length()];
        
        int []yCheck = new int[10];
        
        for(int i=0;i<X.length();i++){
            xArr[i] = X.charAt(i);
        }
        
        for(int i=0; i<Y.length();i++){
            yArr[i]= Y.charAt(i);
        }
       
       
        // 체크한 값 넣어주기
        for(char ch : yArr){
            int number = ch-'0';
            yCheck[number]++;
        }
        
        List<Character> list = new ArrayList<>();
        for(char ch : xArr){
            int number = ch-'0';
            if(yCheck[number]>0) {
                char target = (char)(number+'0');
                list.add(target);
                yCheck[number]--;
            }
        }
        
       
        Collections.sort(list,Collections.reverseOrder());
        if(list.size()==0) return "-1";
        
        
        boolean flag = true;
        for(char ch : list){
            if(flag&&ch=='0') return "0";
            flag=false;
            answer+=ch;
        }
       
        
        return answer;
    }
}

 

해당 코드로 작성하니 

테스트 시... 실패가 나옴.. (시간 초과)

원래 처음에는 list에서 remove를 시켜주어 시간초과가 발생하는지 알아서.. 해당 코드로 변경하였으나 여전히 시간초과가 발생 

또하나의 예상은 아마도 형변환시, 걸리는 시간 때문에 시간초과가 발생하는 걸로 예상된다.. 

 

솔직하게 질문하기에서 StringBuilder를 사용하니깐 빠르게 된다는 말을 보고 해당 방식으로 바꿔주니 테스트 코드를 통과할 수 있었다. 

앞으로는 StringBuilder를 사용하여 문자열을 더해줄 때, append()를 사용해주어야 조금 더 시간이 덜 걸린다는 것을 알 수 있었다. 

이제 본격적으로 성공 코드를 보자. 

 

 

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        char []xArr = new char[X.length()];
        char []yArr = new char[Y.length()];
        
        int []yCheck = new int[10];
        
        for(int i=0;i<X.length();i++){
            xArr[i] = X.charAt(i);
        }
        
        for(int i=0; i<Y.length();i++){
            yArr[i]= Y.charAt(i);
        }
       
       
        // 체크한 값 넣어주기
        for(char ch : yArr){
            int number = ch-'0';
            yCheck[number]++;
        }
        
        List<Character> list = new ArrayList<>();
        for(char ch : xArr){
            int number = ch-'0';
            if(yCheck[number]>0) {
                char target = (char)(number+'0');
                list.add(target);
                yCheck[number]--;
            }
        }
        
       
        Collections.sort(list,Collections.reverseOrder());
        if(list.size()==0) return "-1";
        
        
        boolean flag = true;
        StringBuilder sb = new StringBuilder();
        for(char ch : list){
            if(flag&&ch=='0') return "0";
            flag=false;
            sb.append(ch);
        }
       
        answer = sb.toString();
        return answer;
    }
}

위에와 같은 코드가 성공한 코드이며  위에 코드에서 answer+=ch 를 StringBuilder 사용하여 더해주었다.

 

 

다른 사람들의 풀이

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        String answer = "";

        int[] xArr = new int[10];
        int[] yArr = new int[10];

        for(String x : X.split("")){
            xArr[Integer.parseInt(x)]++;
        }
        for(String y : Y.split("")) {
            yArr[Integer.parseInt(y)]++;
        }

        System.out.println(Arrays.toString(xArr));
        System.out.println(Arrays.toString(yArr));

        StringBuilder sb = new StringBuilder();
        for(int i=9; i>=0; i--){
            while(xArr[i] > 0 && yArr[i] > 0){
                xArr[i]--;
                yArr[i]--;
                sb.append(i);
            }
        }

        if("".equals(sb.toString())) return "-1";
        if("0".equals(sb.toString().substring(0,1))) return "0";

        return sb.toString();
    }
}

1. x ,y 배열을 0~9까지 생성해주었다.

2. 각각을 split로 나누어주어 해당 숫자가 나오는 값에 ++을 해주었다. 그러면 2개가 나오면 2 , 1개가 있다면 1이된다. 

3.  가장 큰 숫자를 만들어주어야 하기 때문에 i=9부터 시작한다. 그 후, while로 xArr[i] , yArr[i]가 0보다 클 때까지 반복하여 StringBuilder에 넣어준다. 또한 xArr , yArr을 둘 다 줄여줘야하는데 그 이유는 두개 숫자가 겹쳐야지 짝꿍이기 때문이다. 

4. 그 후, sb에 값이 없으면 -1, "0" 이면 "0" 이후에 return 을 toString()해준다.