문자열 Permutation && String Builder가 왜 좋은가?

대게 문자열 Permutation을 하면 DFS 나 BruteForce 혹은 DP를 사용해서
Permutation을 했는데,

간단한 코드가 있어서 남긴다.

public static void permutation(String str,String prefix){
        if(str.isEmpty()){
            System.out.println(prefix);
            return;
        }
        for(int i=0; i<str.length(); i++){
            String rem = str.substring(0,i) + str.substring(i+1);
            permutation(rem,prefix+str.charAt(i));
        }

    }

이렇게 짠 사람은 천잰가?

시간복잡도는

$O(n*n!*n)$ 이므로 $O(n^2*n!)$ 이 된다.

Combination도 살짝 올린다.

    public static void combination(String str,String prefix,int index){
        System.out.println(prefix);

        if(prefix.length()==str.length()){
            return;
        }
        for(int i=index; i<str.length(); i++){
            combination(str,prefix+str.charAt(i),i+1);
        }

    }

String Builder 가 왜 좋은가?

물론 모든 경우는 아니다 😁

아무래도 String 클래스를 이용하여 concatination 작업을 사용하면,
각각의 문자열이 저장된 크기의 합만큼 새로운 배열을 준비한뒤
각각의 문자열을 일일이 복사하여 concatination 작업을 이뤄낸다.

즉 str1, str2, str3의 문자열이 있다고 예를들면,
newStr을 만드는데 드는 시간복잡도는 (str1 + str2)*2 + str3 가 될 것이다.
문자열이 많다면 더더욱 느려지고 위 수치는 $O(n^2)$에 수렴한다.

그러나 StringBuilder의 경우 가변 배열을 가지기 때문에,
다른 변수로의 복사를 하지 않는다.
따라서 좀 더 효율적인 Concatination 작업이 가능한 것이다.

자매품으로 멀티쓰레드에 사용가능한 StringBuffer 가 있다.