[프로그래머스] 숫자 짝궁 / 자바(Java)

문제

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

프로그래머스

 

---

해설

주어진 두 정수 X, Y에서 공통된 임의의 정수들을 이용해 가장 큰 수를 만드는 문제입니다.

각자 정수의 개수들만 구해주고 중복되는 정수를 9부터 0까지 역으로 나열하면 가장 큰 수를 만들어줄 수 있습니다.

 

1. X, Y에 각각 대응되는 배열 xarr, yarr를 만들어 각자 가지고있는 정수들의 개수를 구합니다.

2. StringBuilder를 사용해 9부터 0까지 역으로 나아가며 중복된 개수(xarr와 yarr의 동일 인덱스의 최소값)만큼 반복해 문자열을 생성합니다.

3. 0만 중복된 경우와 아예 중복된 숫자가 없는 경우를 고려해 준다.

 

1번 구현부에서 시간복잡도는 각각 for문 하나씩으로 가능하므로 O(n)이 되고,

2번 구현부 역시 모든 숫자가 중복된다 하더라도 1번 구현부의 n보다 작거나 같습니다.

따라서 시간 복잡도는 대략 O(3n)이 될 것 입니다.

주의점

• 공통된 숫자가 0으로만 이루어진 경우는 "0"으로 출력해준다.
• X, Y의 길이가 최대 3,000,000이므로 시간복잡도를 고려한다.
• 중복된 숫자가 아예 없는 경우 "-1"으로 출력해준다.

---

코드

class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        int[] xarr = new int[10];
        int[] yarr = new int[10];
        
        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']++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i=9;i>=0;i--){
            int counter = xarr[i]<yarr[i] ? xarr[i] : yarr[i];
            if(sb.length()==0 && i==0 && counter>0){
                sb.append(0);
                break;
            }
            while(counter>0){
                sb.append(i);
                counter--;
            }
        }
        if(sb.length()==0)sb.append(-1);
        answer = sb.toString();
        return answer;
    }
}