[JAVA , Lv1] 숫자 짝꿍

[문제]

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

 

---

[제한사항]

• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
• X, Y는 0으로 시작하지 않습니다.
• X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

---

[내 풀이]

import java.util.*;
class Solution {
    public String solution(String X, String Y) {
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        int[] x = new int[10];
        int[] y = new int[10];
        
        for(int i=0; i<X.length();i++){
            x[X.charAt(i)-48] +=1;
        }
        for(int i=0; i<Y.length();i++){
            y[Y.charAt(i)-48] +=1;
        }
        for(int i=0; i<x.length; i++){
            if(x[i] >0 && y[i]>0){
                for(int k=0; k<Math.min(x[i],y[i]); k++){
                    q.add(i);
                }
            }
        }
        
        if(q.isEmpty())return "-1"; //비어있으면 -1리턴
        else if(q.peek() == 0) return "0";
        else while(q.size()>0) sb.append(q.poll());
        return sb.toString();
    }
}

---

[풀이 과정]

무작정 2중첩 반복문을 돌리면 제한사항에서의 길이가 굉장히 긴 숫자가 들어올때 n*n번 반복으로 시간초과가 나버린다.

따라서 각 자리숫자는 0~9라는 점을 이용, 크기가 10인 int배열을 선언하여 각 인덱스에 해당하는 숫자가 등장할 시 int배열의 해당 인덱스를 증가시키는 방법으로 반복횟수를 최대한 줄였다.

이렇게하면 인덱스의 값은 인덱스에 해당하는 숫자가 n번 등장했다는것을 알 수 있다.

이후 2개의 배열을 동시에 돌면서 [인덱스 값>0] 인 숫자를 찾고 그중 작은 값을 중복횟수로 간주, 큐에 그 횟수만큼 입력하여  중복되는 수 배열을 만들었다.

큐는 우선순위큐에 reverseOrder()를 이용하여 큐에 삽입시 자동 내림차순 정렬되게 하였다.

 

추가적으로 String 형식에 + 하는 방식 또한 시간을 제법 잡아먹기 때문에 StringBuffer를 사용하여 그 시간을 단축시켰다.

 

---