[Java] String vs StringBuilder, 코딩테스트에서 StringBuilder를 쓰는 이유

Intro

코딩테스트에서 문자열을 변경하는 연산이 많을 때 흔히 StringBuilder를 사용한다.

성능상에 이점이 있어 그렇다고 하는데 구체적으로 왜 이점이 발생하는지 알아보고자 한다.

String vs StringBuilder

String은 이뮤터블 객체(Immutable Object)이다. 즉, 객체의 값을 변경할 수 없고 값을 변경하게 되면 다른 객체가 생성된다.

반면 StringBuilder는 뮤터블 객체(Mutable Object)이다. 즉, 객체의 값을 변경해도 기존 객체가 유지된다.

바로 이점이 성능의 차이를 발생시키는 것이다.

 

객체에 hello를 할당 한 뒤, 이후에 world를 추가한다고 했을 때:

1) String

String s = "hello";
System.out.println(System.identityHashCode(s)); // 245257410
s += "world";
System.out.println(System.identityHashCode(s)); // 1283928880

1. 새로운 String s 객체 생성
2. s가 가진 hello 값을 하나씩 복사
3. hello 뒤에 world 저장

s += "world" 코드 한줄에서 총 10번의 내부 연산("hello" 값 5개 복사, "world"값 5개 저장)이 수행된다.

이때 복사하는 과정으로 인해 시간복잡도는 O(N)이다.

 

2) StringBuilder

StringBuilder sb = new StringBuilder("hello");
System.out.println(System.identityHashCode(sb)); // 245257410
sb.append("world"); // 기존 객체의 상태를 변경
System.out.println(System.identityHashCode(sb)); // 245257410

1. 새로운 StringBuilder sb객체 생성
2. sb객체에 "world" 추가

sb.append("world") 코드는 총 5번의 내부 연산("world"값 5개 저장)이 수행된다.

값을 복사하는 연산이 필요없어지기 때문에 성능향상이 일어난다.

이때 시간복잡도는 O(1)이다.

(StringBuilder의 크기를 늘려야할 때는 O(N)이 되지만 이는 거의 일어나지 않으므로 무시)

 

이러한 연산이 10만번 정도 일어난다 생각했을 때 성능차이를 비교하면 다음과 같다.

1) String

long start = System.currentTimeMillis();

String s = "";
for (int i = 1; i <= 100000; i++) {
	s += "a";
}

long end = System.currentTimeMillis();

System.out.println((end - start) / 1000.0 + "초");

2) StringBuilder

long start = System.currentTimeMillis();

StringBuilder sb = new StringBuilder();
for (int i = 1; i <= 100000; i++) {
	sb.append("a");
}

long end = System.currentTimeMillis();

System.out.println((end - start) / 1000.0 + "초");

 

 

실행환경에 따라 다르겠지만 내 환경에서는 대략 119배의 차이가 났다.

 

멀티스레드 환경이라면 이야기가 달라지겠지만 코딩테스트에선 그럴일이 없으므로 코딩테스트에선 무조건 StringBuilder를 쓰는 것이 좋겠다.