[프로그래머스/Lv.1] 숫자 짝꿍

문제 설명

두 정수 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"

 

입출력 예 설명

입출력 예 #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
지문에 설명된 예시와 같습니다.

 

 

 

⭕ 풀이

class Solution {
    public String solution(String x, String y) {
        String result = "";
        
        int[] xArr = new int[10];
        int[] yArr = new int[10];
        StringBuilder sb = new StringBuilder();
        
        for(int i=0;i<x.length();i++) {
            xArr[x.charAt(i)-'0']++;
        } 
        for(int i=0;i<y.length();i++) {
            yArr[y.charAt(i)-'0']++;
        }
		
        for(int i=9;i>=0;i--) {
            int min = xArr[i]>=yArr[i]?yArr[i]:xArr[i]; 
            while(min-->0) {
                sb.append(i);
            }
        }
		
        result = sb.length()==0?"-1":sb.charAt(0)=='0'?"0":sb.toString(); 
        return result;
    }
}

xArr와 yArr 배열을 만들어 입력받는 문자열 x와 y의 각 자릿수를 카운트한다.

x = "5525", y = "1255" 를 사용하는 예제 5번의경우

왼쪽과같이 각 x와 y의 각 자릿수가 몇번씩 사용되었는지 카운트된 xArr, yArr 배열이 각각 완성되었다.

 

 

 

 

 

다음 세번째 for문에서 i가 9부터 시작하는 이유는 문제에따라 만들 수 있는 가장 큰 수를 만들어야하는데

0부터 시작하게되면 내림차순 정렬을 한번 더 수행해주어야하기때문에 시간을 줄이기위해

9부터 시작하도록하여 내림차순정렬과정을 생략했다.

 

예제 5번이라면 9,8,7,6 을거쳐 5는 xArr와 yArr 둘다 0보다 크지만 yArr에 존재하는 5의 횟수가 더 적다.

때문에 min은 2로 초기화되며 StringBuilder sb 에는 5가 두번 append 된뒤 

4,3을 거쳐 2를 마저 append하면 숫자짝꿍으로 만들 수 있는 가장 큰 수를 문자열형태로 갖게된다.

 

문자열형태라는것은 x = "0001", y="0002" 일경우

"000"을 갖게된다는것이다. 하지만 이경우 "0"을 반환해야하기때문에 삼항연산자로 처리해준다.

sb.length가 0일경우 즉 겹치는 숫자가 없다는 것이기 때문에 result에 "-1"을 할당해주고

만약 sb.charAr(0)라면, 현재 sb는 내림차순으로 정렬된 가장 큰수의 문자열형태인데

첫문자가 0이라는것은 뒤의수들도 있다해도 0이라는것이기때문에 "0"을 할당해준다.

둘다 해당되지 않는다면  sb를 문자열형태로 바꾸어 반환해준다.

 

 

처음에는 sb.length와 sb.charAt으로 구분할 생각을 하지못하고 만들어진 가장 큰 수의 문자열형태인 sb를

임시변수에 담은 뒤 int와 long에는 상당히 큰 정수를 담을 수 없기때문에 BigInteger로 형변환하고

다시 BigInteger를 문자열 result로 형변환해주었다.

하지만 테스트케이스 11~15번에서 자꾸 시간초과가 발생했다.

String couple = sb.toString();
BigInteger big = couple.isEmpty()?new BigInteger("-1"):new BigInteger(couple);

 

형변환이 시간을 많이 잡아먹는다기에  반복문에서 형변환관련 코드를 다 없앴는데도 통과하지못해 결국 위의 BigInteger를 없애고 length와 charAt을 사용하니 바로 통과되었다.

반복문 안에 존재하는 코드도 아니었고 한줄짜리 코드였기때문에 여기서 시간초과가 발생했을것이라는 생각은 전혀하지못한채 위의 반복문들만 계속 수정했었던 문제였다..

 

 

 

 

 

 

 

 

-출처

https://school.programmers.co.kr/learn/courses/30/lessons/131128