[기술 면접 코딩 인터뷰 준비] 순환 문자열 찾기 알고리즘 - String rotation

이 문제를 처음 접했을 때 제가 선택한 방법은 모든 순환 경우를 직접 생성해서 하나씩 비교하는 방식이었습니다. A 문자열의 길이가 N이면 N개의 순환 문자열을 만들고, 각각 B와 비교하면 된다고 생각했습니다. 코드도 금방 완성됐고, 제출할 준비가 됐다고 느꼈습니다.

그런데 면접관이 "시간 복잡도가 어떻게 되나요?"라고 물으신 순간, 저는 잠시 멈칫했습니다. 순환 문자열을 N번 생성하고, 각 생성에서 O(N) 복사가 발생하며, 비교도 O(N)이 걸린다는 사실을 뒤늦게 계산했고, 전체가 O(N²)이라는 것을 그 자리에서 깨달았습니다. 나중에 알게 된 것이지만, 이 실수는 이 문제를 처음 푸는 분들이 거의 예외 없이 반복하는 함정이었습니다.

문제 이해

문자열 A, B 두 개가 주어졌을 때 B가 A의 순환 문자열인지 확인하는 문제입니다. 순환 문자열이란 A의 가장 앞 문자를 끝으로 옮기거나, 끝 문자를 앞으로 옮기는 방식으로 얻을 수 있는 문자열입니다. 예를 들어 "abcde"의 순환 문자열 중 하나는 "deabc"입니다.

예제 1: Input: A = 'abcde', B = 'cdeab' Output: true

예제 2: Input: A = 'waterbottle', B = 'erbottlewat' Output: true

예제 3: Input: A = 'abcde', B = 'abced' Output: false

브루트포스 접근과 그 한계

처음 작성한 코드는 다음과 같습니다. 동작은 하지만 시간 복잡도가 O(N²)이라는 치명적인 단점이 있습니다.

public boolean rotateString(String A, String B) {
    if(A == null || B == null || A.length() != B.length()) return false;
    if(A.length() == 0 && B.length() == 0) return true;
    
    for(int i = 0; i < A.length(); i++){
        if((A.substring(i) + A.substring(0, i)).equals(B)){
            return true;
        }
    }
    return false;
}

면접에서 이 코드를 제출하면 "더 효율적인 방법 없나요?"라는 질문이 바로 따라옵니다. 저도 그 질문을 받았고, 잠시 침묵이 흘렀습니다. 그 순간이 지금도 선명하게 기억납니다.

제가 추가로 틀렸던 케이스: 빈 문자열과 길이 체크

브루트포스보다 더 당황스러웠던 실수가 있었습니다. 초기 구현에서 길이 체크를 빠뜨린 채 제출했더니, 길이가 다른 두 문자열이 입력됐을 때 잘못된 결과가 나왔습니다. 예를 들어 A = "abc", B = "abcabc"처럼 B가 A+A인 경우에 true를 반환하는 오류였습니다. 빈 문자열 케이스도 마찬가지였습니다. A = "", B = ""일 때 어떻게 처리할지 미리 생각해두지 않으면 예외 처리가 빠집니다.

올바른 처리 순서는 다음과 같습니다.

• A와 B의 길이가 다르면 즉시 false 반환
• 두 문자열이 모두 비어 있으면 true 반환
• 그 뒤에 회전 판별 로직 진행

최적화된 해결법: A+A 트릭

A를 두 번 연결하면 모든 가능한 순환 문자열이 포함됩니다. A = "waterbottle"이면 A+A = "waterbottlewaterbottle"이고, 이 문자열 안에는 "erbottlewat", "rbottlewater" 등 가능한 모든 순환 문자열이 substring으로 포함됩니다.

따라서 B가 A의 순환 문자열인지 확인하는 문제는 B가 A+A의 substring인지 확인하는 문제로 바뀝니다. 한 줄로 해결됩니다.

public boolean rotateString(String A, String B) {
    return A.length() == B.length() && (A + A).contains(B);
}

길이 체크가 앞에 오는 것이 중요합니다. 길이가 다른 두 문자열은 절대로 순환 관계가 될 수 없고, 길이 체크 없이 substring만 확인하면 잘못된 결과가 나옵니다. 빈 문자열 케이스는 이 코드가 자연스럽게 처리합니다. A.length() == B.length()가 0 == 0을 만족하고, (A + A).contains(B)는 빈 문자열을 포함한다고 판단하기 때문입니다.

시간 복잡도는 Java의 contains() 구현 성능에 따라 달라지며, 일반적으로 O(N)으로 분석됩니다. 면접에서 "KMP를 적용하지 않아도 되나요?"라고 물으실 수 있는데, 표준 라이브러리의 contains는 대부분의 구현에서 효율적인 탐색을 제공하므로 별도 최적화 없이도 O(N)에 근접한 성능을 얻을 수 있습니다.

면접에서 이 문제를 만났을 때

A+A 트릭을 떠올리기까지 시간이 걸렸습니다. 막상 한 줄로 코드를 적고 나서 면접관이 "왜 이게 동작하는지 설명해 주실 수 있나요?"라고 물었고, 저는 A+A 안에 모든 순환이 포함된다는 원리를 그림으로 설명했습니다. 그때 면접관이 고개를 끄덕이던 모습이 기억납니다.

이 문제에서 실수를 피하려면 세 가지를 기억하면 됩니다. 첫째, 길이가 다르면 무조건 false입니다. 둘째, 빈 문자열을 미리 처리합니다. 셋째, A+A 트릭을 설명할 때 "왜 이게 동작하는지"를 같이 말할 수 있어야 합니다. 코드 한 줄보다 그 원리를 설명하는 능력이 면접에서 더 중요합니다.