[Java] String은 왜 느릴까? StringBuilder와 가변 배열의 비밀

1. String은 왜 느릴까

알고리즘 문제를 풀때 String 객체에 + 연산을 하면 왜 메모리 초과나 시간 초과가 나는걸까?

String은 char[]로 이루어져 있다(Java 9 이상부터는 byte[]).

그리고 final 키워드 때문에 수정이 불가하며 수정을 원하면 매번 새로운 배열 객체를 생성해야한다.

 

그럼 + 연산자는 어떻게 구현되는 것일까

매번 새로운 String 객체를 만들어내는것이다. 이것이 메모리 초과와 시간 초과의 원인이다.

 

이로인해 많은 비효율이 발생했고, 이를 해결하기 위해 StringBuilder가 탄생했다.

StringBuilder는 수정가능한 가변 배열(Dynamic Array)을 사용한다.

 

가변 배열을 구현해봤다.

public class MyDynamicArray {
    private int[] data;
    private int capacity;
    private int size;

    public MyDynamicArray(int initialCapacity) {
        this.capacity = initialCapacity;
        this.data = new int[capacity];
        this.size = 0;
    }
    
    public void add(int value) {
        if (size == capacity) {
            resize();
        }
        data[size++] = value;
    }

    private void resize() {
        capacity = capacity * 2;
        int[] newData = new int[capacity];

        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }

        this.data = newData;
    }
}

 

위와 같이 가변 배열은 초기 크기로 시작해 크기가 꽉차면 2배 크기의 배열을 만들어 값들을 복사한다.

 

때문에 N번의 + 연산 작업도 StringBuilder에서는 logN의 시간복잡도로 효율적이다.

또한 StringBuilder는 new StringBuilder(1000000)처럼 미리 크기를 지정하면 1000000까지 복사하는 비용을 절약할 수 있다.

 

2. delete나 insert의 비효율성

위에서 말했다시피 String과 StringBuilder는 어디까지나 배열이다.

배열 head나 중간에 값이 delete되거나 insert가 된다면 값들이 앞으로 당겨지거나 뒤로 밀리는 O(N) 비용이 발생한다.

이런 계산이 필요한 경우 포인터를 활용한 탐색이 더 유리할 수 있다.

 

3. 언제 어떤것을 쓸까

알고리즘 문제가 아닌 개발 환경에서는 확장에는 열려 있으나, 변경에는 닫혀 있어야하는 OCP원칙에 따라 String이 안정적이다.

한 객체에서 문자열 조작이 반복적으로 발생할 경우 StringBuilder를 사용하자.