Java로 구현하는 최장 회문 부분 수열(LPS) 찾기 프로그램

최장 회문 부분 수열(Longest Palindromic Subsequence, LPS)이란 원본 문자열에서 문자 순서를 유지한 채 일부 문자를 제거하여 만들 수 있는 부분 수열 중, 앞에서 읽어도 뒤에서 읽어도 같은 가장 긴 문자열을 의미합니다. 예를 들어 "HelloHelloo"의 경우 가장 긴 회문 부분 수열은 "llell"입니다.

이 문제는 문자열과 그 문자열을 뒤집은 문자열 간의 최장 공통 부분 수열(LCS)을 구하는 것과 동일하기 때문에, 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다.

예제 코드

public class Demo{
    static String longest_seq(String str_1, String str_2){
        int str_1_len = str_1.length();
        int str_2_len = str_2.length();
        char str_1_arr[] = str_1.toCharArray();
        char str_2_arr[] = str_2.toCharArray();
        int L[][] = new int[str_1_len + 1][str_2_len + 1];
        for (int i = 0; i <= str_1_len; i++){
            for (int j = 0; j <= str_2_len; j++){
                if (i == 0 || j == 0){
                    L[i][j] = 0;
                }
                else if (str_1_arr[i - 1] == str_2_arr[j - 1]){
                    L[i][j] = L[i - 1][j - 1] + 1;
                }
                else{
                    L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
                }
            }
        }
        int my_index = L[str_1_len][str_2_len];
        char[] longest_seq = new char[my_index + 1];
        int i = str_1_len, j = str_2_len;
        while (i > 0 && j > 0){
            if (str_1_arr[i - 1] == str_2_arr[j - 1]){
                longest_seq[my_index - 1] = str_1_arr[i - 1];
                i--;
                j--;
                my_index--;
            }
            else if (L[i - 1][j] > L[i][j - 1]){
                i--;
            } else {
                j--;
            }
        }
        String my_result = "";
        for (int x = 0; x < longest_seq.length; x++){
            my_result += longest_seq[x];
        }
        return my_result;
    }
    static String longestPalSubseq(String str){
        String rev_str = str;
        rev_str = reverse_str(rev_str);
        return longest_seq(str, rev_str);
    }
    static String reverse_str(String str){
        String my_result = "";
        char[] trial = str.toCharArray();
        for (int i = trial.length - 1; i >= 0; i--){
            my_result += trial[i];
        }
        return my_result;
    }
    public static void main(String[] args){
        String str = "HelloHelloo";
        System.out.println("Longest palindromic subsequence is ");
        System.out.println(longestPalSubseq(str));
    }
}

실행 결과

Longest palindromic subsequence is
llell

코드 동작 원리

위 코드의 Demo 클래스에는 longest_seq 메서드가 포함되어 있으며, 이 메서드는 두 개의 문자열과 두 개의 문자 배열을 선언합니다. 두 배열을 이중 반복문으로 순회하면서 동적 계획법 기반의 LCS 알고리즘으로 가장 긴 회문 부분 수열을 찾습니다.

핵심은 2차원 배열 L에 각 위치별 LCS 길이를 저장한다는 점입니다. 한 번 계산된 값은 테이블에 저장되어 재계산되지 않기 때문에, 모든 경우를 반복해서 탐색하는 완전 탐색(Brute Force) 방식보다 연산 효율이 크게 향상됩니다.

주요 메서드 살펴보기

• longestPalSubseq: 입력 문자열을 받아 뒤집은 후, 원본 문자열과 뒤집힌 문자열을 인자로 전달하며 longest_seq를 호출합니다.
• reverse_str: 매개변수로 전달받은 문자열을 역순으로 뒤집어 반환하는 보조 메서드입니다.
• main: 테스트용 문자열을 정의하고 longestPalSubseq를 호출한 뒤, 그 결과를 콘솔에 출력합니다.

이처럼 문자열을 뒤집어 LCS를 구하는 접근 방식만 활용하면, 별도의 복잡한 회문 검증 로직 없이도 최장 회문 부분 수열을 손쉽게 구할 수 있습니다.