[코딩 알고리즘] 최단 회문 만들기 (Shortest Palindrome)

이번 포스팅에서는 최소한의 문자를 추가해서 회문을 만드는 알고리즘 문제를 풀어보도록 하겠다.

 

문제: 주어진 문자열 S가 있을때 문자열 맨 앞부분에 다른 문자열을 추가하여 회문으로 만들 수가 있다. 이와 같은 문자열 변환을 통해서 가장 짧은 회문을 반환하여라.

예제 1:
입력: "aacecaaa" 
출력: "aaacecaaa"

예제 2:
입력: "abcd" 
출력: "dcbabcd"

문제 자체는 이해하기 어렵지 않다. 회문이 아닌 문자열에 어떤 문자열을 추가해서 회문으로 만들면 된다. 

언제나 그렇듯 가장 단순 무식하게 풀어보는 방법을 일단 먼저 찾아보는 것이 중요하다. 쉽게 떠올릴 수 있는 방법은 주어진 문자열 안에서 존재하는 가장 긴 회문 문자열을 찾는 것이다. 모든 문자를 한 번씩 방문한 다음 회문인지 아닌지 여부를 찾아야 한다. 따라서 모든 문자를 방문하므로 문자열의 길이 * 회문 찾는 비용만큼의 시간 복잡도의 비용이 필요로 할 것이다. 즉 O(N^2)이다.

 

우리가 이전에 풀었던 회문 찾기를 복기해서 풀어보면 문제 자체는 풀 수 있지만 최적화되었다고 말하기엔 조금 무리가 있다. 면접관에게 깊은 인상을 주기 위해서는 더 최적화된 코드를 작성해야 할 것이다.

 

문제를 조금 바꿔서 생각해보면 우리의 통찰력이 발휘될지 모른다. 0번째 (즉 맨 처음) 위치에서 시작하는 가장 긴 회문을 찾는 문제라고 생각해보고 접근해보도록 하자.

 

예: "abacd"
0번째부터 시작하는 가장 긴 회문은 "aba"이다.
이다음이 중요하다. 가장 긴 회문을 찾았으니 나머지 문자열을 뒤집어서 앞부분에 붙이면 가장 짧은 회문임을 알 수 있다. 즉 "cd"를 반전시킨 다음 맨 앞부분에 붙이면 "dcabacd" 회문이 완성된다.

 

이제 이 문제는 0번째에서 시작하는 가장 긴 회문을 찾는 문제를 풀면 답을 알 수 있다. 그리고 이것을 찾는 가장 좋은 방법은 KMP 알고리즘을 응용하는 것이다.

 

이전 포스팅에서 KMP 알고리즘에 대해서 알아보았으니 익숙지 않다면 한번 보고 오도록 하자.

 

정확하게는 KMP 알고리즘에서 사용하는 "실패 함수 (failure function)"을 사용하면 된다. 실패 함수의 특성은 접두사(prefix)와 접미사(suffix)가 얼마나 중복되는지를 배열로 저장해서 알려준다는 것이다.

 

실패 함수의 특성을 0번째 부터 시작하는 가장 긴 회문을 찾는데 사용하려면 주어진 문자열을 반전 시킨뒤 둘을 합친다음 실패함수를 적용시키면 된다.

예: "abacd" 
- 주어진 문자열 + 반전 시킨 문자열 = "abacd" + "dcaba"
- 실패함수 결과 : [0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 3]

실패 함수가 반환한 배열에서 우리가 관심 있는 것은 그래서 맨 마지막 배열 값이다. 맨 마지막 배열 값이 "abacd" + "dcaba" 문자의 처음과 마지막이 (접두사와 접미사) 얼마나 같은지에 대한 답이기 때문이다. 위의 예제에서는 3이기 때문에 "aba"가 가장 긴 회문임을 알 수 있다. 

 

실패 함수를 사용하면 된다는 걸 알면 이젠 누워서 숨쉬기 정도로 풀 수 있다.

 public String shortestPalindrome(String s) {
        String temp = s + "-" + new StringBuilder(s).reverse().toString();
        int[] table = failure(temp);

        return new StringBuilder(s.substring(table[table.length - 1])).reverse().toString() + s;
    }

    private int[] failure(String str){
        int n = str.length();
        int j = 0;
        int[] arr = new int[n];
        for(int i = 1; i < n; i++){
            while(j > 0 && str.charAt(j) != str.charAt(i)) j = arr[j - 1];
            if(str.charAt(j) == str.charAt(i)) arr[i] = ++j;

        }
        return arr;
    }

 

참고로 반전된 문자열을 합치기 전에 구분자를 넣어줘야 한다. 편한 대로 알파벳을 제외한 어떤 문자라도 상관없다. 물론 공백도 상관없다. 위 코드의 시간 복잡도는 O(N)이고 공간 복잡도 역시 O(N)이다.

 

이번 문제는 사실 쉽지 않은 문제이다. 이번 문제를 간단하게 풀었다면 앞으로 있을 인터뷰에서 상당히 좋은 결과를 기대해볼 만하다. 정답 확인은 온라인 코드 저지 사이트인 Leetcode에서 확인해 볼 수 있다.