[Programmers] 숫자 짝꿍 - Java

문제

프로그래머스

 

풀이

X, Y의 문자열에서 공통된 숫자들로 만들 수 있는 최댓값이 되는 수를 만드는 문제이다.

 

문자열의 길이가 300만이다. 300만개의 숫자 데이터를 저장하는 것은 메모리 사용량이 많을 것이라고 생각했다.

그리고 문자열에는 0~9까지의 수만 나올 수 있으므로, 길이가 10인 배열을 선언해 세는 것이 더 좋은 방법이라고 생각했다.

 

공통된 숫자들의 개수를 구하기 위해서는 두 배열에서 최솟값을 넣으면 공통된 숫자의 개수가 된다.

1110(0 : 1개, 1: 3개)

1100(0 : 2개, 1: 2개)

0은 1개

1은 2개

가 공통된 수가 되기 때문이다.

 

1. X, Y 문자열에 저장되어 있는 수의 개수를 저장할 배열을 선언해 개수를 센다.

 

2. X, Y 개수 저장한 배열의 최솟값을 새로운 배열에 넣어준다.

 

3. 9부터 0까지 숫자를 감소시키면서 공통된 숫자의 개수가 있으면 문자열을 만든다.

 

4. 문자열이 비었을 경우, 문자가 0으로 시작할 경우("0", "0000")과 같은 경우에 처리를 해준다.

 

소스코드

class Solution {
    public String solution(String X, String Y) {
        int[] cntX = new int[10];
        int[] cntY = new int[10];
        int[] cnt = new int[10];
        
        for (char ch : X.toCharArray()) {
            cntX[ch - '0']++;
        }
        
        for (char ch : Y.toCharArray()) {
            cntY[ch - '0']++;
        }
        
        for (int i = 0; i < 10; i++) {
            cnt[i] = Math.min(cntX[i], cntY[i]);
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 9; i >= 0; i--) {
            for (int j = 0; j < cnt[i]; j++) {
                sb.append(i);
            }
        }
        
        String answer = sb.toString();
        
        if (answer.isEmpty()) {
            answer = "-1";
        } else if (answer.charAt(0) == '0') {
            answer = "0";
        } 
        
        return answer;
    }
}

 

실행결과