기술면접 - 팰린드롬 확인

팰린드롬 확인 (Check if a String is a Palindrome)

이 글에서는 C언어를 사용하여 문자열이 팰린드롬인지 확인하는 방법을 자세히 설명합니다. 팰린드롬이란, 문자열을 뒤집어도 동일한 문자열을 의미합니다. 예를 들어, "radar"나 "A man a plan a canal Panama"는 팰린드롬입니다. 이 글에서는 공백과 대소문자 처리 방법, 그리고 코드 최적화 방안까지 다룹니다.

1. 팰린드롬이란?

팰린드롬(Palindrome)은 문자열을 처음부터 읽거나 끝에서부터 읽었을 때 동일한 결과를 내는 문자열입니다. 예를 들어:

• "racecar" → 팰린드롬
• "A level eye level A" → 공백과 대소문자를 무시하면 팰린드롬
• "hello" → 팰린드롬 아님

문제는 공백, 대소문자, 특수문자 등을 어떻게 처리할지에 따라 복잡도가 달라집니다.

2. 문제 정의

주어진 문자열이 팰린드롬인지 확인하는 프로그램을 작성해야 합니다. 다음 조건을 만족해야 합니다:

1. 대소문자를 구분하지 않음 (예: 'A'와 'a'는 동일하게 처리).
2. 공백과 특수문자를 무시 (알파벳과 숫자만 고려).
3. 효율적인 알고리즘으로 처리 (O(n) 시간 복잡도 목표).

3. C언어 구현

아래는 위 조건을 만족하는 C언어 코드입니다. 이 코드는 입력 문자열을 받아 팰린드롬 여부를 판단합니다.

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

// 팰린드롬 확인 함수
bool isPalindrome(char *str) {
    int left = 0;
    int right = strlen(str) - 1;

    while (left < right) {
        // 왼쪽 포인터가 알파벳/숫자가 아닌 경우 이동
        while (left < right && !isalnum(str[left])) {
            left++;
        }
        // 오른쪽 포인터가 알파벳/숫자가 아닌 경우 이동
        while (left < right && !isalnum(str[right])) {
            right--;
        }
        // 대소문자 무시하고 비교
        if (tolower(str[left]) != tolower(str[right])) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    // 테스트 케이스
    char *test1 = "A man, a plan, a canal: Panama";
    char *test2 = "race a car";
    char *test3 = "Was it a car or a cat I saw?";

    printf("\"%s\" is %s\n", test1, isPalindrome(test1) ? "a palindrome" : "not a palindrome");
    printf("\"%s\" is %s\n", test2, isPalindrome(test2) ? "a palindrome" : "not a palindrome");
    printf("\"%s\" is %s\n", test3, isPalindrome(test3) ? "a palindrome" : "not a palindrome");

    return 0;
}

위 코드의 출력 결과는 다음과 같습니다:

"A man, a plan, a canal: Panama" is a palindrome
"race a car" is not a palindrome
"Was it a car or a cat I saw?" is a palindrome

4. 코드 설명

코드를 단계별로 자세히 분석해 보겠습니다.

4.1. 필요한 헤더 파일

• <stdio.h>: 입출력 함수(printf 등).
• <string.h>: 문자열 길이 계산(strlen).
• <ctype.h>: 문자 처리 함수(isalnum, tolower).
• <stdbool.h>: 불리언 타입(bool).

4.2. isPalindrome 함수

이 함수는 두 포인터 기법(Two-Pointer Technique)을 사용하여 문자열의 양 끝에서 시작해 가운데로 이동하며 팰린드롬 여부를 확인합니다.

• 포인터 초기화: left는 문자열의 시작, right는 문자열의 끝을 가리킵니다.
• 알파벳/숫자 체크: isalnum 함수로 현재 문자가 알파벳이나 숫자인지 확인합니다. 그렇지 않으면 포인터를 이동합니다.
• 대소문자 처리: tolower 함수로 문자를 소문자로 변환해 비교합니다.
• 비교: 양쪽 문자가 다르면 false를 반환하고, 끝까지 문제가 없으면 true를 반환합니다.

4.3. 메인 함수

main 함수에서는 테스트 케이스를 정의하고 isPalindrome 함수를 호출해 결과를 출력합니다.

5. 최적화 방안

위 코드는 이미 O(n) 시간 복잡도를 가지며 효율적입니다. 그러나 추가적인 최적화 방안을 고려할 수 있습니다:

1. 메모리 최적화: 입력 문자열을 복사하지 않고 원본을 직접 처리해 메모리 사용량을 줄였습니다.
2. 조기 종료: 팰린드롬이 아닌 경우 즉시 false를 반환해 불필요한 연산을 줄입니다.
3. 문자열 전처리 (선택 사항): 모든 문자를 소문자로 변환하고 알파벳/숫자만 남기는 전처리 단계를 추가할 수 있습니다. 하지만 이는 추가 메모리와 시간이 필요하므로 트레이드오프를 고려해야 합니다.

예를 들어, 전처리 방식의 코드는 다음과 같습니다:

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

bool isPalindromePreprocess(char *str) {
    int len = strlen(str);
    char temp[1000];
    int j = 0;

    // 알파벳/숫자만 추출하고 소문자로 변환
    for (int i = 0; i < len; i++) {
        if (isalnum(str[i])) {
            temp[j++] = tolower(str[i]);
        }
    }
    temp[j] = '\0';

    // 팰린드롬 체크
    int left = 0;
    int right = j - 1;
    while (left < right) {
        if (temp[left] != temp[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

이 방식은 코드가 직관적이지만, 추가 메모리(O(n))와 전처리 시간(O(n))이 필요합니다.

6. 시간 및 공간 복잡도

• 첫 번째 구현 (Two-Pointer):
  • 시간 복잡도: O(n) - 문자열을 한 번 순회.
  • 공간 복잡도: O(1) - 추가 메모리 사용 없음.
• 전처리 방식:
• 시간 복잡도: O(n) - 전처리와 비교 모두 선형 시간.
• 공간 복잡도: O(n) - 새로운 문자열 저장용 메모리 필요.

7. 결론

이 글에서는 C언어를 사용해 문자열이 팰린드롬인지 확인하는 두 가지 방법을 살펴보았습니다. 첫 번째 방법(Two-Pointer)은 메모리 효율적이며 빠른 실행 시간을 제공합니다. 두 번째 방법(전처리)은 코드가 더 직관적이지만 추가 메모리가 필요합니다. 문제의 요구사항에 따라 적절한 방식을 선택하면 됩니다.

추가적으로, 입력 문자열의 유효성 검사(예: NULL 체크)나 다양한 문자 인코딩(예: UTF-8) 처리를 고려할 수 있습니다. 이 코드는 일반적인 ASCII 문자열에 최적화되어 있습니다.