[기술 면접 준비] 문자열 원 편집 거리 검사 - One Edit Distance

코딩 인터뷰에서 처음 이 문제를 받았을 때, 저는 “아, 쉽다”라고 생각했습니다. 그리고 그게 화근이었습니다. 빠르게 코드를 완성하고 제출했는데, 면접관이 “같은 문자열 두 개를 넣으면 어떻게 되나요?”라고 물었습니다. 제 코드는 true를 반환했습니다. 틀렸습니다. 문제는 “정확히 1번”의 편집인데, 저는 “최대 1번”으로 잘못 이해하고 짰던 거죠.

그 이후에도 두 가지 실수를 더 했습니다. Null 입력을 전혀 검증하지 않아서 NullPointerException이 면접관 화면에 출력됐고, 삽입·삭제 케이스에서 인덱스를 건너뛰는 로직을 잊어 틀린 답을 냈습니다. 커뮤니티에서도 이 세 가지 함정은 반복해서 나오는 이야기입니다. 오늘은 그 경험을 바탕으로 이 문제를 제대로 정리해보겠습니다.

문제 정의

문제: 두 개의 문자열이 주어졌을 경우, 편집 횟수가 정확히 1인지 확인하는 함수를 작성하십시오.

편집 연산은 다음 세 가지입니다.

• 문자 추가
• 문자 삭제
• 문자 변경

여기서 “정확히 1번” 이라는 조건이 핵심입니다. "abc"와 "abc"는 편집 횟수가 0이므로 false를 반환해야 합니다. ""와 ""도 마찬가지입니다. 처음에 이 함정을 놓쳐서 면접에서 낭패를 봤습니다.

커뮤니티에서 반복되는 실수들

LeetCode 토론과 면접 경험 공유 글에서 공통으로 등장하는 실수가 있습니다.

1. “정확히 1번”을 “최대 1번”으로 혼동: 이게 가장 흔합니다. s == t인 경우를 따로 처리하지 않으면 true가 나옵니다. 저도 처음에 이걸 빠뜨렸습니다.

2. Null 입력 미검증: 실제 서비스 코드와 면접 코드 모두 Null 체크가 필요합니다. 빠뜨리면 s.length()를 호출하는 순간 NullPointerException이 납니다.

3. 삽입/삭제 시 인덱스 건너뛰기 누락: 두 문자열 길이가 다를 때, 차이가 발생한 위치에서 긴 쪽 인덱스를 하나 건너뛰어야 합니다. 이 로직을 빠뜨리면 이후 비교가 전부 엉클어집니다.

4. 루프 종료 후 남은 문자 미처리: 루프가 끝난 뒤 한 쪽 문자열에 문자가 남아있을 수 있습니다. 이 나머지도 편집 횟수에 포함해야 합니다.

접근 방법

문자열의 길이 차이가 1보다 크면 한 번의 편집으로 변환할 수 없습니다. 따라서 먼저 Math.abs(s.length() - t.length()) > 1 를 검사합니다. 그 이후에는 두 문자열을 앞에서부터 순차적으로 비교하면서 차이가 발생한 첫 번째 위치에서 길이가 긴 문자열을 하나 건너뛰는 방식을 사용합니다. 차이가 두 번 이상 발생하면 false 를 반환합니다.

코드 구현 (Java)

public boolean oneEditDistance(String s, String t) {
    // 함정 1: null 입력 방어
    if (s == null || t == null) return false;

    int slen = s.length();
    int tlen = t.length();

    // 길이 차이가 2 이상이면 불가능
    if (Math.abs(slen - tlen) > 1) return false;

    int i = 0, j = 0, diff = 0;
    while (i < slen && j < tlen) {
        if (s.charAt(i) != t.charAt(j)) {
            diff++;
            if (diff > 1) return false;
            if (slen > tlen) {
                // s가 더 긴 경우: s의 현재 문자를 건너뛰고 t는 그대로 유지 (삭제 연산)
                i++;
                continue;
            } else if (slen < tlen) {
                // t가 더 긴 경우: t의 현재 문자를 건너뛰고 s는 그대로 유지 (삽입 연산)
                j++;
                continue;
            }
            // 길이가 같은 경우: 교체 연산이므로 양쪽 모두 진행
        }
        i++;
        j++;
    }
    // 함정 2: 루프 후 남은 문자도 편집 횟수에 포함
    // diff + 남은 문자 수 == 1 이면 정확히 1번 편집
    return diff + (slen - i) + (tlen - j) == 1;
}

마지막 줄 return diff + (slen - i) + (tlen - j) == 1;이 핵심입니다. 루프 안에서 차이를 못 찾더라도 한쪽에 문자가 남아있으면 그게 바로 1번의 삽입/삭제에 해당합니다. 예를 들어 s = "ab", t = "abc"라면 루프가 i=2, j=2에서 끝나고 t에 c 하나가 남아 0 + 0 + 1 = 1이 되어 true를 반환합니다. 그리고 s = "abc", t = "abc"라면 0 + 0 + 0 = 0이 되어 false입니다.

시간·공간 복잡도

위 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n) 입니다. 여기서 n 은 두 문자열 중 짧은 쪽의 길이이며, 공간 복잡도는 O(1) 으로 추가 메모리를 사용하지 않습니다.

추가 팁 및 인터뷰 인사이트

면접에서는 구현 정확성과 함께 코드 가독성, 예외 처리를 평가합니다. 그리고 꼭 면접관에게 먼저 질문하는 습관을 들이세요.

• “두 문자열이 동일할 경우 false를 반환해야 합니까?” — 이 한 마디가 “정확히 1번” 조건을 제대로 이해했는지를 보여줍니다.
• “Null 입력이 들어올 수 있습니까?” — 실무 감각을 어필하는 질문입니다.
• 로직을 설명할 때 “삽입은 긴 쪽 인덱스를 건너뜁니다, 삭제도 마찬가지입니다, 교체는 양쪽을 동시에 진행합니다”라고 세 케이스를 명확하게 말하면 면접관이 따라오기 쉽습니다.

이 알고리즘은 레벤슈타인 거리(Levenshtein distance)의 단순화 버전입니다. 오타 교정 기능을 설계할 때 기본 원리로 활용되므로, 실무 연관성을 언급하면 인상을 남길 수 있습니다.