[프로그래머스] 숫자짝꿍

문제링크

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 함수를 완성해주세요.

입출력

X	Y	result
"100"	"2345"	"-1"
"100"	"203045"	"0"
"100"	"123450"	"10"
"12321"	"42531"	"321"
"5525"	"1255"	"552"

1차 시도 => 실패

로직

두 배열에서 같은 숫자가 나오면 기존 배열을 초기화 하고, 그 숫자를 리턴하는 방식으로 구현을 생각했다.

코드

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        StringBuilder sb = new StringBuilder();
        
        char[] arrayX= X.toCharArray();
        char[] arrayY= Y.toCharArray();

        List<Integer> number = new ArrayList<>();

        for(int i=0;i<arrayX.length;i++){
            for(int j=0;j<arrayY.length;j++){
                if(arrayX[i]==arrayY[j]){
                    number.add(Integer.parseInt(String.valueOf(arrayX[i])));

                    arrayY[j]= 'A';
                    break;
                }
            }
        }

        Collections.sort(number, Collections.reverseOrder());

        for(int i=0;i<number.size();i++) sb.append(number.get(i));
    
        if(sb.length() == 0) sb.append("-1");
        if(sb.substring(0,1).equals("0")) sb.delete(1,sb.length());
        return sb.toString();
    }
}

정확성 테스트

시간초과 원인

잦은 형변환과, substring, delete 등 문자열 메소드를 시간복잡도 고려 없이 많이 사용한 것으로 추측된다

2차 시도 => 성공

로직

형변환과 다른 문자로 초기화 하는 것을 줄이기 위해 answer 라는 숫자배열을 선언하고, 각 문자열에 있는 숫자의 갯수를 세어준다
1. y배열을 돌면서 answer의 숫자 배열을 세어주고
2. x배열을 돌면서 answer에도 값이 존재하는지 체크한다. 존재하면 count를 제거하고 list에 추가해준다
3. list를 정렬하고 해당 배열을 정렬해준다

코드

import java.util.*;

class Solution {
   public String solution(String X, String Y) {
        ArrayList<Integer> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int[] answer = new int[10];

        for(int i=0;i<Y.length();i++){
            int n= Y.charAt(i)-48;
            answer[n]++;
        }
        int zero = answer[0];
        for(int i =0; i<X.length(); i++) {
            int n = X.charAt(i)-48;
            if(answer[n]>0) {
                answer[n]--;
                list.add(n);
            }
        }

        list.sort(Comparator.reverseOrder());

        for(int i=0;i<list.size();i++) sb.append(list.get(i));
        if(sb.length() == 0) return "-1";
        if(sb.length() == answer[0]) return "0";
        return sb.toString();
    }
}

정확성 테스트