[내일배움캠프 TIL] Java String 연산의 함정과 StringBuilder를 통한 성능 개선 (프로그래머스 '숫자 짝꿍')

1. 🚨 문제 상황 (Issue)

프로그래머스의 '숫자 짝꿍' 문제를 풀면서 알고리즘의 시간 복잡도를 $O(N)$으로 최적화했음에도 불구하고 반복문 내에서 데이터를 처리할 때 시간 초과(Time Out)가 발생했다.

당시 문제가 되었던 코드 조각은 다음과 같다.

Java

 

// 시간 초과의 주범
for (int i = zzak_arr.length - 1; i >= 0; i--) {
    int cc = zzak_arr[i];
    for (int j = 0; j < cc; j++) {
        answer += i; // ❌ 반복문 안에서 String에 + 연산 누적
    }
}

2. 🔍 원인 분석: String의 불변성 (Immutability)

자바에서 String 객체는 한 번 생성되면 값을 변경할 수 없는 불변(Immutable) 객체다.

따라서 answer += i; 코드가 실행될 때 기존 문자열 뒤에 숫자가 단순히 붙는 것이 아니다. 내부적으로는 매번 새로운 메모리 공간을 할당받아 새로운 String 객체를 만들고, 기존 내용을 복사하는 과정이 일어난다.

• 이 문제에서 입력값 $X, Y$의 길이는 최대 3,000,000(3백만)이다.
• 즉, 최악의 경우 문자열 복사 및 새 객체 생성 행위를 수백만 번 반복하게 된다.
• 이로 인해 메모리 낭비(Garbage Collection 유발)와 심각한 시간 지연이 발생해 시간 초과로 이어진 것이다.

3. 🚀 해결책: StringBuilder 사용하기

문자열을 빈번하게 수정, 추가해야 할 때는 값이 변할 수 있는(Mutable) 클래스인 StringBuilder를 사용해야 한다.

💻 수정된 코드

Java

 

// 1. StringBuilder 객체 생성
StringBuilder sb = new StringBuilder(); 

for (int i = zzak_arr.length - 1; i >= 0; i--) {
    int cc = zzak_arr[i];
    for (int j = 0; j < cc; j++) {
        if (i != 0) zero_check = 0;
        
        // 2. append() 메서드로 뒤에 문자를 가볍게 붙여줌
        sb.append(i); 
    }
}

// 3. 최종 출력을 위해 String으로 변환
String answer = sb.toString();

4. ❓ StringBuilder는 왜 더 빠를까? (원리)

StringBuilder는 내부에 문자를 저장하는 가변 크기의 배열(char[] 또는 byte[])을 버퍼로 가지고 있다.

1. 메모리 재사용: append()를 호출할 때 새 객체를 매번 만드는 것이 아니라, 내부에 있는 배열의 값만 바꾼다. (마치 자바스크립트의 array.push()처럼 동작)
2. 효율적인 확장: 배열의 공간이 부족해질 때만 내부적으로 배열의 크기를 키우기 때문에, 객체 생성 횟수가 극적으로 줄어든다.

결과적으로 객체 생성 오버헤드가 사라져 수백만 번의 연산도 단 몇 밀리초(ms) 만에 끝낼 수 있게 된다.

5. 📊 핵심 요약 (String vs StringBuilder 전후 비교)

특징	String	StringBuilder
가변성	불변 (Immutable)	가변 (Mutable)
연산 방식	연산 시마다 새로운 객체 생성	기존 버퍼(배열)에 값 추가
적합한 상황	문자열 연산이 적고 조회가 많을 때	반복문 내에서 문자열 추가/수정이 잦을 때
성능 (이번 문제)	❌ 시간 초과 (Fail)	⭕ 수 밀리초 만에 통과 (Pass)