[알고리즘]Palindrome Algorithm / 팰린드롬 알고리즘 + 예시문제

Palindrome Algorithm이란?

회문 판별 알고리즘. 주어진 문자열이 회문인지 아닌지 판별하는 알고리즘으로,

간단하게 생각하면...

ex) 우영우의 기러기-토마토-스위스-인도인-별똥별

 

문자열 중 회문인 문자열을 찾기 위해 다이나믹 프로그래밍을 이용하여 시간복잡도를 O(N^2)으로 줄일 수 있다.

(시간복잡도란? 입력값과 연산 수행시간의 상관관계를 나타내는 척도(길이)를 시간 복잡도라고 한다.)

---

예시를 들어보자면, 

문제 :

키보드로 문자열을 입력받아서 앞과 뒤방향이 동일한 가장 긴 부분 문자열의 길이를 출력하시오.

단, 입력받는 문자열의 길이는 100미만이라고 가정한다.

예)
입력 : abacabaek

출력 : 7

---

예시 입력과 결과

예시 입력: "babad"

단계별 설명

초기 상태

입력 문자열: babad 길이: 5

단계 1: 길이 1인 부분 문자열 팰린드롬 체크

모든 길이 1인 부분 문자열은 팰린드롬이다

| dp 테이블 |

|---|---|---|---|---|

| 1 | 0 | 0 | 0 | 0 |

| 0 | 1 | 0 | 0 | 0 |

| 0 | 0 | 1 | 0 | 0 |

| 0 | 0 | 0 | 1 | 0 |

| 0 | 0 | 0 | 0 | 1 |

maxLength = 1

단계 2: 길이 2인 부분 문자열 팰린드롬 체크

• "ba": str[0] != str[1]
• "ab": str[1] != str[2]
• "ba": str[2] != str[3]
• "ad": str[3] != str[4]

팰린드롬인 길이 2 부분 문자열이 없다.

dp 테이블은 그대로:

| dp 테이블 |

|---|---|---|---|---|

| 1 | 0 | 0 | 0 | 0 |

| 0 | 1 | 0 | 0 | 0 |

| 0 | 0 | 1 | 0 | 0 |

| 0 | 0 | 0 | 1 | 0 |

| 0 | 0 | 0 | 0 | 1 |

maxLength = 1

단계 3: 길이 3인 부분 문자열 팰린드롬 체크

• "bab": str[0] == str[2]이고 dp[1][1] == 1
  • dp[0][2] = 1
  • maxLength = 3
• "aba": str[1] == str[3]이고 dp[2][2] == 1
  • dp[1][3] = 1
  • maxLength = 3
• "bad": str[2] != str[4]

| dp 테이블 |

|---|---|---|---|---|

| 1 | 0 | 1 | 0 | 0 |

| 0 | 1 | 0 | 1 | 0 |

| 0 | 0 | 1 | 0 | 0 |

| 0 | 0 | 0 | 1 | 0 |

| 0 | 0 | 0 | 0 | 1 |

maxLength = 3

단계 4: 길이 4인 부분 문자열 팰린드롬 체크

• "baba": str[0] != str[3]
• "abad": str[1] != str[4]

| dp 테이블 |

|---|---|---|---|---|

| 1 | 0 | 1 | 0 | 0 |

| 0 | 1 | 0 | 1 | 0 |

| 0 | 0 | 1 | 0 | 0 |

| 0 | 0 | 0 | 1 | 0 |

| 0 | 0 | 0 | 0 | 1 |

maxLength = 3

단계 5: 길이 5인 부분 문자열 팰린드롬 체크

• "babad": str[0] != str[4]

| dp 테이블 |

|---|---|---|---|---|

| 1 | 0 | 1 | 0 | 0 |

| 0 | 1 | 0 | 1 | 0 |

| 0 | 0 | 1 | 0 | 0 |

| 0 | 0 | 0 | 1 | 0 |

| 0 | 0 | 0 | 0 | 1 |

maxLength = 3

최종 결과

가장 긴 팰린드롬 부분 문자열은 길이 3입니다. 예를 들어, "bab" 또는 "aba"가 있다. [출력 : 3]

 

#include <stdio.h> 

int stringLength(const char* str);
int longestPalindrome(const char* str);


int main(void) {
    /*
    문자열을 입력받아 str 배열에 저장
    longestPalindrome 함수를 호출하여 입력된 문자열에서 가장 긴 
    팰린드롬 부분 문자열의 길이를 계산한다. 그후, 결과를 출력.
    */
    char str[100];
    printf("문자열을 입력: ");
    scanf("%s", str);

    int result = longestPalindrome(str);
    printf("가장 긴 팰린드롬 부분 문자열의 길이: %d\n", result);

    return 0;
}

// 문자열의 길이를 계산하는 함수
/*
문자열의 길이를 계산하여 반환합니다.
while 루프를 사용하여 문자열 끝('\0')에 도달할 때까지 문자의 개수를 셉니다.
*/
int stringLength(const char* str) {
    int length = 0;
    while (str[length] != '\0') {
        length++;
    }
    return length;
}

// 가장 긴 팰린드롬 부분 문자열의 길이를 찾는 함수
int longestPalindrome(const char* str) {
    int n = stringLength(str);
    if (n == 0) return 0;

    int dp[100][100] = {0}; // dp 테이블 초기화
    int maxLength = 1; // 팰린드롬의 최소 길이는 1

    /*
    dp[i][j]는 str[i]부터 str[j]까지의 부분 문자열이 팰린드롬인지 여부를 나타냅니다.
    모든 길이 1인 부분 문자열은 팰린드롬이므로 dp[i][i]를 1로 설정합니다.
    maxLength를 1로 초기화합니다.
    */


    // 길이 1인 모든 부분 문자열은 팰린드롬
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // 길이 2인 부분 문자열 체크
    /*
    길이 2인 부분 문자열이 팰린드롬인지 확인하고, 팰린드롬이면 dp[i][i + 1]을 1로 
    설정하고 maxLength를 2로 갱신합니다.
    */
    
    for (int i = 0; i < n - 1; i++) {
        if (str[i] == str[i + 1]) {
            dp[i][i + 1] = 1;
            maxLength = 2;
        }
    }

    // 길이 3 이상인 부분 문자열 체크
    /*
    길이 3 이상인 부분 문자열의 경우, 양 끝 문자가 같고 내부 부분 문자열(dp[i + 1][j - 1])이 
    팰린드롬이면 해당 부분 문자열도 팰린드롬입니다.
    이 경우 dp[i][j]를 1로 설정하고, 현재 부분 문자열의 길이가 maxLength보다 크면 maxLength를 갱신합니다.
    */
    for (int length = 3; length <= n; length++) {
        for (int i = 0; i < n - length + 1; i++) {
            int j = i + length - 1;

            if (str[i] == str[j] && dp[i + 1][j - 1]) {
                dp[i][j] = 1;
                if (length > maxLength) {
                    maxLength = length;
                }
            }
        }
    }

    return maxLength; //최종 결과 반환
}