StringBuilder

자바에서는 문자열을 쉽고 효율적으로 구성하고자 StringBuilder 클래스를 제공합니다. 반복문을 이용하여 String을 구성하는 다음 예시를 살펴봅시다.

String az = "";
for (char c = 'a'; c <= 'z'; c++) {
    az += c;
}
System.out.println(az); // "abcd..xyz"

이 코드는 정상적으로 ‘a’부터 ‘z’까지 문자를 이어 붙인 문자열을 구성합니다. 하지만 이렇게 코드를 작성하면 매 반복마다 새로운 문자열 객체가 생성되고, 새로운 문자의 배열을 복사합니다. 즉, 가장 처음 만든 빈 문자열 “ ”부터 ‘a’가 추가된 “a”, ‘b’가 추가된 “ab”, ‘c’가 추가된 “abc”, …, ‘z’가 추가된 “abc…xyz”까지 모든 문자열 객체가 생성됩니다.

배열을 복사하는 데 배열의 모든 원소를 참조해야 하므로, 배열 길이 N에 대해 O(N)의 시간이 소요됩니다. 문자열도 내부적으로 배열을 사용하므로 길이가 N인 새로운 문자열을 만드는 데 O(N)이 소요됩니다. 이 과정을 빈 문자열부터 길이를 하나씩 늘려가며 반복하므로 (길이가 1인 문자열을 만드는 데 필요한 시간) + (길이가 2인 문자열을 만드는 데 필요한 시간) + … + (길이가 n인 문자열을 만드는 데 필요한 시간) = O(N²)의 시간이 걸립니다. 단순히 “abc…xyz”를 만드는 데 제곱의 시간 복잡도가 소요되는 것입니다.