C 프로그램으로 문장에서 가장 긴 회문(Palindrome) 단어 찾는 방법

주어진 문장 안에서 가장 긴 회문(팰린드롬)을 찾아 출력하는 것이 이번 문제의 목표입니다.

회문(Palindrome)이란?

회문이란 문자열을 거꾸로 뒤집어도 원래와 동일하게 읽히는 단어나 문자열을 의미합니다.

예시 – 'Nitin'은 문자열을 뒤집어도 'Nitin' 그대로이므로 회문입니다.

여기서의 과제는 주어진 문장에서 가장 긴 회문 단어를 찾아내는 것입니다.

예를 들어 다음과 같은 문장이 있다고 가정해 보겠습니다.

malayalam liemadameil iji

이 문장에는 세 개의 회문 단어가 포함되어 있지만, 그중 가장 긴 것은 liemadameil입니다.

알고리즘

START
STEP 1 -> 변수 i, j, k, l, max를 0으로, index를 -1로, check를 0으로, count를 0으로 선언 및 초기화
Step 2 -> i = 0부터 시작하여 i < strlen(str) 동안 반복
    max = 0, k = i, j = i + 1로 설정
    str[j]가 공백(' ')도 널 문자('\0')도 아닌 동안 j를 1씩 증가
    l = j - 1로 설정
    IF str[k]가 공백도 널 문자도 아니라면
        k <= l인 동안 반복
            IF str[k] == str[l]이라면
                max를 1 증가
                IF count <= max라면
                    index = i, count = max로 설정
                End If
            ELSE
                max = 0, count = -1로 설정 후 반복 종료(break)
            End Else
            k는 1 증가, l은 1 감소
        End Loop While
End If
i = j로 설정
Step 3 -> For 루프 종료
Step 4 -> i = index부터 시작하여 i != -1 && str[i] != ' ' && str[i] != '\0'인 동안 반복하며 str[i] 출력
Step 5 -> For 루프 종료
STOP

C 언어 구현 예제

#include <stdio.h>
#include <string.h>
int main(int argc, char const *argv[]) {
    char str[] = {"malayalam liemadameil iji"};
    int i, k, l, j, max = 0, index = -1, check = 0, count = 0;
    for(i = 0; i < strlen(str); i++) {
        max = 0;
        k = i;
        j = i + 1;
        while(str[j] != ' ' && str[j] != '\0'){
            j++;
        }
        l = j - 1;
        if(str[k] != ' ' && str[k] != '\0') {
            while(k <= l) {
                if (str[k] == str[l]) {
                    max++;
                    if(count <= max) {
                        index = i;
                        count = max;
                    }
                } else {
                    max = 0;
                    count = -1;
                    break;
                }
                k++;
                l--;
            }
        }
        i = j;
    }
    for (i = index; i != -1 && str[i] != ' ' && str[i] != '\0'; i++) {
        printf("%c", str[i]);
    }
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

liemadameil

동작 방식 설명

이 프로그램은 두 개의 포인터(k, l)를 활용하는 방식으로 동작합니다. 각 단어의 시작 위치(k)와 끝 위치(l)에서부터 서로를 향해 이동하면서 문자를 하나씩 비교합니다. 모든 비교에서 문자가 일치하면 해당 단어는 회문이 되며, 일치하지 않는 순간 즉시 검사를 중단하고 다음 단어로 넘어갑니다.

검사 과정에서 가장 긴 회문의 시작 인덱스를 index 변수에 저장해 두었다가, 마지막에 해당 위치부터 공백 또는 문자열의 끝까지 한 글자씩 출력함으로써 가장 긴 회문 단어만 화면에 표시하게 됩니다.