[면접 코딩] O(N²)인 줄 모르고 제출했다가 혼난 문자열 압축, String Compression 완벽 분석

"제출 버튼 누르고 Time Limit Exceeded 보신 분들, 저도 처음에 똑같았습니다."

문자열 압축은 문제 자체는 단순해서 "이거 5분이면 풀겠네" 하고 덤볐다가, 막상 면접관 앞에서 "시간 복잡도는요?" 라는 질문에 얼어버리는 경우가 정말 많습니다. 오늘은 이 문제를 초보자도 이해할 수 있게 차근차근 뜯어보고, 면접에서 진짜 플러스가 되는 팁까지 정리하겠습니다.

문제

반복되는 문자의 개수를 숫자로 표시하는 방식으로 기본적인 문자열 압축을 수행하는 함수를 작성하세요. 예를 들어 문자열 aabcccccaaa 는 a2b1c5a3 로 압축할 수 있습니다. 만약 압축된 문자열이 원본 문자열보다 길거나 같으면 원본 문자열을 그대로 반환합니다. 문자열은 소문자 알파벳만 있다고 가정합니다.

1단계: 일단 생각나는 대로 짜봅시다 (그리고 왜 틀렸는지 봅시다)

문자열을 처음부터 끝까지 한 글자씩 읽으면서, 같은 문자가 몇 번 나오는지 세서 결과 문자열에 문자 + 숫자 형태로 이어 붙이면 끝 아닐까요?

public String naiveCompress(String str) {
    int i = 0;
    String result = "";
    while (i < str.length()) {
        int count = 0;
        char c = str.charAt(i);
        while (i < str.length() && c == str.charAt(i)) {
            i++;
            count++;
        }
        result += c;
        result += count;
    }
    return str.length() > result.length() ? result : str;
}

얼핏 보면 $O(N)$ 같아 보입니다. 문자를 한 번씩만 스캔하니까요. 하지만 여기에 큰 함정이 숨어 있습니다.

자바에서 String 은 불변(immutable) 입니다. result += c 같은 연산을 할 때마다 기존 문자열 전체를 새로 복사해서 새로운 String 객체를 만듭니다. 그러니까 첫 번째 문자에서 1글자 복사, 두 번째에서 2글자 복사, 세 번째에서 3글자 복사… 이런 식으로 늘어나서 총 복사량은 $1+2+3+…+N$ 이 되어 실제 시간 복잡도는 $O(N^2)$ 이 됩니다.

면접관이 "시간 복잡도가 어떻게 되나요?" 하고 물어보면, 여기서 대부분 걸러진다고 합니다.

2단계: StringBuilder로 $O(N)$ 만들기

해결책은 간단합니다. String 대신 StringBuilder를 쓰면 내부 버퍼에 바로 이어 붙이기 때문에 매번 새 객체를 만들지 않아도 됩니다.

public String compress(String str) {
    int i = 0;
    StringBuilder sb = new StringBuilder();
    while (i < str.length()) {
        int count = 0;
        char c = str.charAt(i);
        while (i < str.length() && c == str.charAt(i)) {
            i++;
            count++;
        }
        sb.append(c).append(count);
    }
    return str.length() > sb.length() ? sb.toString() : str;
}

이제 시간 복잡도는 $O(N)$ 으로 내려갑니다. 하지만 여기서 끝이 아닙니다.

3단계: 한 번 더 최적화, 미리 길이 계산하기

위 코드를 잘 보면, 압축 결과가 원본보다 길어도 일단 StringBuilder를 만들고 다 붙인 다음에 비교하고 있어요. 만약 원본 문자열이 abcdefg 였다면 압축 결과는 a1b1c1d1e1f1g1 로 원본보다 길어지는데도, 불필요하게 StringBuilder를 다 생성한 거죠.

면접관에게 "압축 길이를 먼저 계산해서, 원본보다 짧을 때만 StringBuilder를 만들면 어떨까요?" 라고 먼저 제안해보세요. 이렇게요:

int compressionLength = countCompression(str);
if (compressionLength >= str.length()) return str;

StringBuilder compressed = new StringBuilder(compressionLength);
// ... 기존 압축 로직 실행

여기서 또 하나 중요한 포인트가 있습니다. StringBuilder 생성자에 압축 길이를 미리 넣어주는 것이에요. StringBuilder는 내부 배열이 꽉 차면 크기를 두 배로 늘리면서 배열을 다시 복사하는데, 이렇게 최종 크기를 미리 알려주면 그 비용을 완전히 없앨 수 있습니다.

면접 팁: 이 문제에서 '진짜' 보여줘야 하는 것

• String의 불변성을 알고 있는지, 그리고 그게 왜 $O(N^2)$을 만드는지 구체적인 숫자로 설명할 수 있어야 합니다.
• StringBuilder의 내부 동작 방식(용량이 부족하면 2배로 확장하며 배열을 복사함)을 언급하면 "이 지원자는 언어를 깊게 이해하고 있구나" 라는 인상을 줍니다.
• 마지막에 "압축 길이를 미리 계산해서 조건부로 실행했다" 라고 말하는 것만으로도 불필요한 연산을 최소화하려는 엔지니어링 사고를 어필할 수 있어요.
• 면접관이 출제 의도를 확장한다면, 메모리 제약이 있는 환경(in-place 압축)이나 대용량 스트리밍 환경에서 어떻게 할지도 물어볼 수 있으니 미리 생각해두면 좋습니다.

---

정리

문자열 압축 문제는 겉보기엔 단순하지만, 면접관이 진짜 보고 싶은 건 이런 겁니다:

• 내가 쓰는 언어의 기본 자료형 특성을 알고 있는가?
• 시간 복잡도를 정확히 계산할 수 있는가?
• 더 나아가서 최적화 포인트를 스스로 찾아서 제안할 수 있는가?

다음에 이 문제를 만나면, 그냥 코드만 짜지 말고 면접관에게 "String은 불변이니까 StringBuilder를 써야 하고, 추가로 미리 길이를 계산해서 최적화할 수 있습니다" 라고 먼저 어필해보세요. 면접관 표정이 달라지는 걸 느끼실 수 있을 겁니다.