문제는 여기 클릭
BigInterger로 이루어진 두 String X, Y를 파라미터로 받아 둘이 공통으로 가지고 있는 수를 이용해서 가장 큰 수를 만들어 반환시켜야 한다.


### 문제 설명


첫번째 시도

class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        int x[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; //각 0123456789의 개수
        int y[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        for(int i = 0 ; i < X.length() ; i++){
            x[X.charAt(i)-'0']++;
        }
        for(int i = 0 ; i < Y.length() ; i++){
            y[Y.charAt(i)-'0']++;
        }
        for(int i = 9 ; i >= 0 ; i--){
            while(x[i] > 0 && y[i] > 0){
                answer = answer+i;
                x[i]--;
                y[i]--;
            }
        }
        
        if(answer.equals("")){
            answer = "-1";
        }
        else if(answer.charAt(0) == '0'){
            answer = "0";
        }
        return answer;
    }
}

x와 y 정수 배열을 선언하여 X와 Y에 해당 숫자가 얼마나 있는지를 나타내려 하였다.
(ex. X = "999123"일 경우 9가 3개 있으므로 x[9]에는 3이 들어간다. x[1],x[2],x[3]에는 각 1이 들어간다.)
char 자료형을 int로 변환해야하므로 -'0'을 해주었고
3번째 for문에서 같은 숫자를 x,y모두 1이상 갖고 있을 경우 answer에 더해주고 x[i] y[i]의 수를 감소시키는 방향으로 틀을 잡았다.
밑의 if문에서는 서로 매치하는 수가 없으면 -1을 반환하고,
맨 앞 자릿수가 0이면 뒤의 자릿수도 모두 0이기 때문에(answer = answer+1로 내림차순 정렬된다.) 바로 0을 반환한다.

그러나 위 코드로 짜면 시간 초과로 오답이 된다...

이유는 자바의 String 객체가 새로운 문자를 더하는 방식에 있다.(위의 answer+i와 같은 경우들)
문자열과 문자열을 더하면 새로운 문자열을 생성하는데, 이 과정에서 이전 문자열이 더이상 참조되어있지 않으면 GC가 처리하고, 이전 두 개의 문자열 길이의 합을 가진 새로운 문자열 객체를 생성하고, 메모리를 해제하고 다시 할당하고... 이 과정에서 큰 연산시간이 소요된다.

이를 해결하기 위해서 StringBuilder가 사용된다.
StringBuilder는 문자열을 더할 때, immutable객체인 String과 달리 메모리를 할당, 해제하지 않고 메모리를 가변적으로 늘려나가는 구조이기 때문에 연산시간이 크게 단축된다.

String 대신 StringBuilder를 사용한 코드

class Solution {
    public String solution(String X, String Y) {
        StringBuilder answer = new StringBuilder();
        int x[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; //각 0123456789의 개수
        int y[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        for(int i = 0 ; i < X.length() ; i++){
            x[X.charAt(i)-'0']++;
        }
        for(int i = 0 ; i < Y.length() ; i++){
            y[Y.charAt(i)-'0']++;
        }
        for(int i = 9 ; i >= 0 ; i--){
            while(x[i] > 0 && y[i] > 0){
                answer.append(i);
                x[i]--;
                y[i]--;
            }
        }

        if(answer.toString().equals("")){
            return "-1";
        }
        else if(answer.toString().charAt(0) == '0'){
            return "0";
        }
        return answer.toString();
    }
}

결과

별개로 StringBuilder 말고 StringBuffer 객체도 있는데, 전자는 싱글 쓰레드 환경에 적합하고, 후자는 DeadLock(교착상태)를 방지하기 위해 Lock을 사용함으로써 성능은 떨어지지만 멀티 쓰레드 환경에서도 사용할 수 있다는 차이점이 있다.
연산이 많은 경우에서 동기화를 고려하지 않는다면
StringBuilder > StringBuffer >>>>>>>> String 순으로 성능이 좋다.

0개의 댓글