[프로그래머스] 131128번 - 숫자 짝꿍 [Java]

프로그래머스

 

 

---

 

 

문제

 

 

제출한 코드

class Solution {
    public String solution(String X, String Y) {
        
        int[] xArr = new int[10];
        for (String x : X.split("")) {
            xArr[Integer.parseInt(x)]++;
        }
        
        int[] yArr = new int[10];
        for (String y : Y.split("")) {
            yArr[Integer.parseInt(y)]++;
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 9; i >= 0; i--) {
            while (xArr[i] > 0 && yArr[i] > 0) {
                sb.append(i);
                xArr[i]--;
                yArr[i]--;
            }
        }
        
        if (sb.length() == 0) return "-1";
        if (sb.charAt(0) == '0') return "0";
        
        return sb.toString();
    }
}

 

 

풀이

처음에는 이중으로 for문을 사용하여 문제를 풀었으나 일부 테스트 케이스가 시간초과가 돼서 통과를 못했다.

시간복잡도를 O(n) 으로 줄이기 위해 for문을 한 번만 사용하는 방식으로 다시 풀어서 제출했다.

 

먼저 문자열 X에서 한 자리씩 비교하여 해당 숫자의 index 자리에 있는 xArr를 1씩 증가시키도록 했다.

문자열 Y도 동일한 방식으로 yArr에 해당 자리의 숫자를 1씩 증가했다.

 

가장 큰 정수를 반환해야 하므로 맨뒤에서부터 시작하여, xArr와 yArr 모두 해당 인덱스의 숫자가 0 초과일 때까지, StringBuilder에 해당 숫자를 append 하고, 해당 자리의 숫자를 1 감소시켰고, 

이렇게 해서 만들어진 sb를 반환하도록 했다.

 

만약 만들어진 StringBuilder의 문자열의 길이가 0이라면 짝꿍이 존재하지 않으므로 "-1"을,

문자열이 '0' 으로 시작하면 짝꿍이 0으로만 구성되어 있으므로 "0"이 반환된다.