개요
회문(Palindrome)이란 앞에서 읽으나 뒤에서 읽으나 같은 문자열을 의미합니다. 예를 들어 "racecar", "level", "madam" 같은 단어들이 대표적인 회문입니다.
이번 글에서는 C 언어에서 포인터만을 사용하여 주어진 문자열이 회문인지 확인하는 방법을 알아보겠습니다. 인덱스 연산 없이 포인터 두 개를 앞뒤로 움직이는 방식으로 문제를 해결할 수 있습니다.
예를 들어 입력이 s = "racecar"라면, 앞뒤 어느 방향으로 읽어도 동일하므로 출력은 참(True), 즉 1이 됩니다.
해결 접근 방식
두 개의 포인터를 활용한 투 포인터(Two Pointer) 기법으로 문제를 해결합니다. 알고리즘의 단계는 다음과 같습니다.
- length := 문자열의 전체 길이를 저장합니다.
- forward := 문자열의 첫 번째 문자를 가리키는 포인터입니다.
- reverse := 문자열의 마지막 문자를 가리키는 포인터입니다.
- reverse의 위치가 forward의 위치보다 크거나 같은 동안 반복합니다:
- reverse가 가리키는 문자와 forward가 가리키는 문자가 같다면 → forward를 한 칸 앞으로 이동(++), reverse를 한 칸 뒤로 이동(--)
- 그렇지 않다면 → 두 문자가 다르므로 반복문을 빠져나옵니다.
- 반복 종료 후 forward의 위치가 reverse의 위치보다 크거나 같다면 → 모든 문자가 일치한 것이므로 참(1)을 반환합니다.
- 그렇지 않다면 거짓(0)을 반환합니다.
핵심 아이디어는 간단합니다. 문자열의 양 끝에서부터 시작해 서로를 향해 포인터를 이동시키며 문자를 비교하고, 중간에서 만나기까지 모든 문자가 일치하면 그 문자열은 회문입니다.
C 언어 구현 예제
아래 코드를 통해 실제 구현 과정을 살펴보겠습니다.
#include <stdio.h>
#include <string.h>
int solve(char *string){
int length;
char *forward, *reverse;
length = strlen(string);
forward = string;
reverse = forward + length - 1;
for (forward = string; reverse >= forward;) {
if (*reverse == *forward) {
reverse--;
forward++;
} else
break;
} if (forward > reverse)
return 1;
else
return 0;
}
int main(){
char string[] = "racecar";
printf("%d", solve(string));
}입력
"racecar"
출력
1
코드 설명
strlen(string)함수로 문자열 길이를 구한 뒤,reverse = forward + length - 1을 통해 마지막 문자의 메모리 주소를 계산합니다.*reverse == *forward조건은 역참조(Dereferencing)를 통해 두 포인터가 가리키는 실제 문자 값을 비교합니다.- 두 문자가 일치하면 포인터를 각각 안쪽으로 이동시키고, 불일치 시 즉시 반복문을 종료합니다.
- 짝수 길이 회문의 경우 두 포인터가 교차하고, 홀수 길이 회문의 경우 가운데 문자에서 만나므로 최종 조건
forward > reverse로 성공 여부를 판단할 수 있습니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이이며, 최악의 경우에도 각 문자를 한 번씩만 비교하기 때문입니다. 공간 복잡도는 추가 메모리를 사용하지 않으므로 O(1)입니다.