[C++] 회문(팰린드롬) 판별에 관한 모든 것

이번 글의 주제는 '팰린드롬 판별'에 관한 이야기이다. 쉬운 주제이지만, 팰린드롬 판별을 구현할 수 있는 방법은 여러 가지이니 이에 대하여 작성해보려 한다.

---

1. 팰린드롬이란?

팰린드롬(Palindrome, 회문)은 처음부터 끝까지 거꾸로 읽어도 똑같이 읽히는 수 또는 문자열을 의미한다.

 

예를 들면, "racecar"나 "abcdcba", 한글로 하면 "수박이박수", "다시합창합시다" 정도가 되겠다.

 

이 팰린드롬을 판별하는 것은 여러 방법이 있지만, 먼저 가장 팰린드롬의 기본에 충실하게 코드를 작성하여 보자.

---

2. 팰린드롬 판별 1 - Naive

팰린드롬을 판별하려면, 처음 글자부터 마지막 글자까지 거꾸로 셌을 때 같은 수거나 문자열이면 가능하다. 입력이 문자열일 경우 다음과 같이 함수를 작성할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
bool is_palindrome(string str) {
    bool flag = true; 
    for (int i = 0; i < str.size(); i++) { // 처음부터 끝까지 검사
        if (str[i] != str[str.size()-1-i]) { // 문자열이 다를 경우
            flag = false; // 팰린드롬이 
            break;
        }
    }
 
    return flag;
}
 
int main() {
    
    cout << boolalpha;
    cout << is_palindrome("racecar") << endl; // true
    cout << is_palindrome("abbac") << endl; // false
    cout << is_palindrome("11122111") << endl; // true
 
    return 0;
}

 

또는 입력이 정수일 경우 다음과 같이 함수를 작성할 수 있다. 정수일 경우 10으로 나누었을 때의 나머지가 마지막 자리이므로 이를 차례로 쌓아나가면 거꾸로 된 수를 만들 수 있고, 따라서 팰린드롬인지 판별할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
bool is_palindrome(int num) {
    int num_original = num;
    int num_rev = 0;
    while (num > 0) {
        num_rev = num_rev*10 + num % 10;
        num /= 10;
    }
 
    return num_original == num_rev;
}
 
int main() {
 
    cout << boolalpha;
    cout << is_palindrome(12121) << endl; // true
    cout << is_palindrome(1232) << endl; // false
    cout << is_palindrome(0) << endl; // true
 
    return 0;
}

 

그렇지만, 이를 최적화하는 방법은 없을까? 생각을 해보자.

---

3. 팰린드롬 판별 2 - Modified

팰린드롬을 검사하는데 모든 문자를 한 번씩 모두 봐야 할까? 어차피 가운데 글자에서부터 오른쪽에 있는 글자들은 이미 왼쪽에서 짝을 지어 검사할 때 이미 봤던 수이다.

 

따라서, 가운데 글자 보다 왼쪽에 있는 글자들만 확인하면 팰린드롬인지 확인할 수 있다. 이 경우 Naive한 방법보다 연산 횟수를 반으로 줄일 수 있다.

(ex. "racecar", "abccba")

 

이를 코드로 나타내면 다음과 같다. 입력이 문자열인 경우 다음과 같이 작성할 수 있다. 결국 반 이하까지만 확인하면 된다. 

 

#include <bits/stdc++.h>
using namespace std;
 
bool is_palindrome(string str) {
    bool flag = true; 
    for (int i = 0; i < str.size() / 2; i++) { // 처음부터 가운데 전까지 검사
        if (str[i] != str[str.size()-1-i]) { // 문자열이 다를 경우
            flag = false; // 팰린드롬이 아님.
            break;
        }
    }
 
    return flag;
}
 
int main() {
    
    cout << boolalpha;
    cout << is_palindrome("racecar") << endl; // true
    cout << is_palindrome("abbac") << endl; // false
    cout << is_palindrome("11122111") << endl; // true
 
    return 0;
}

 

만약, 입력이 정수라면 어떻게 해야할까? 위의 정수와 같은 방법을 사용할 수 있지만, 문자열이 입력일 경우보다 고려해주어야 할 사항이 많다.

 

먼저, 팰린드롬이 항상 아닐 경우를 생각하여보자.

 

먼저, 정수는 0으로 시작하는 경우가 없다. 따라서, 일의 자리가 0이라면 ("120", "3160") 항상 팰린드롬이 아니라고 생각할 수 있다. 그러나, 한 자리 정수는 팰린드롬이므로 "0"은 팰린드롬이다. 또한, 음수는 팰린드롬이 아니다. 이 두 경우가 입력으로 들어왔을 때 적절히 예외처리를 해주어야 한다.

 

이후, 정수를 뒤집는 방법을 이용하여 반 이하만 뒤집어 주면 된다. (일의 자리 나머지 & 쌓아나가기)

 

이후 기존의 수와 비교를 해주면 되는데, 어떻게 비교할 수 있을까?

 

"123321"의 경우, 끝의 "321"("123321")만 뒤집어 "123"으로 뒤집은 후, 뒤집지 않은 자리와 같은지 확인하면 된다. 

 

입력인 정수가 x가 하고, 일부만 뒤집은 수를 x_rev라 하면 다음과 같이 코드를 작성할 수 있다.

 

int x_rev = 0;
while (x > x_rev) {
    x_rev = x_rev * 10 + x % 10;
    x /= 10;
}

 

이후 팰린드롬인지 판별을 하여보자.

 

 

입력의 자릿수가 짝수라고 가정할 때, ("123321", "1221") 이 경우 x_rev에는 뒤집힌 반 이상의 자리, x에는 반 이하의 자리 수가 담겨있으므로 x와 x_rev가 같은지만 판별하면 된다.

 

이제, 입력의 자릿수가 홀수라고 가정라자. ("1234321", "54345")

 

이 경우 x_rev에는 어떤 수가 담겨있을까? x가 x_rev보다 클 때까지만 while문이 실행되므로, x_rev는 가운데 수를 포함한 뒤집힌 수가 담겨있다고 할 수 있다. ("1234321" => "1234", "54345" => "543")

 

x에는 가운데 자리가 포함이 되지 않은 수가 담겨있으므로, ("1234321" => "123", "54345" => "54) 이 수가 팰린드롬인지 판별하려면 x_rev의 일의 자리를 제외하고 x와 비교해야 한다.

 

일의 자리를 제외한 수는 그 수를 10으로 나눈 몫과 같으므로, x_rev를 10으로 나눈 몫과 x를 비교하면 된다.

 

이를 종합하여 함수로 나타내면 다음과 같다.

 

bool is_palindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) { // 음수이거나 0이 아닌 0으로 끝나는 수일 경우...
        return false; // 거짓 반환
    }
 
    int x_rev = 0;
    while (x > x_rev) {
        x_rev = x_rev * 10 + x % 10;
        x /= 10;
    } // 반만 뒤집음
 
    return x == x_rev || x == x_rev/10; // x의 길이가 짝수일 때 || 홀수일 때
}
 
int main() {
 
    cout << boolalpha;
    cout << is_palindrome(12121) << endl; // true
    cout << is_palindrome(1232) << endl; // false
    cout << is_palindrome(0) << endl; // true
 
    return 0;
}

---

4. 팰린드롬 판별 3 - Using STL

C++ 에는 STL(Standard Template Library)을 활용하여 팰린드롬을 더 쉽게 판별할 수 있다.

 

문자열을 뒤집을 수 있는 reverse 함수를 활용하면 더욱 쉽게 문자열을 뒤집을 수 있지만, Naive와 같은 방법으로 뒤집기에 효율적이지는 못하다.

 

함수만 작성하면 다음과 같이 작성할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
bool is_palindrome(string str) {
    string str_rev = str;
    reverse(str_rev.begin(), str_rev.end());
 
    return str_rev == str;
}

 

Modified와 같은 방법을 활용하기 위해선, equal 함수를 활용하면 판별할 수 있다. equal 함수에 관한 별도의 포스팅이 있으니 이를 읽고 온다면 밑의 코드가 이해가 될 것이다.

([C++] 두 배열을 함수 한 방에 아주 쉽게 비교하자! equal)

 

함수만 작성하면 다음과 같다.

 

#include <bits/stdc++.h>
using namespace std;
 
bool is_palindrome(string str) {
    return equal(str.begin(), str.begin() + str.size()/2, str.rbegin());
}

 

매우 간단히 끝낼 수 있다.

 

5. 팰린드롬 판별 4 - Using Recursive Function

팰린드롬을 판별할 때, 재귀 함수를 활용할 수도 있다.

 

어떤 문자열이 팰랜드롬인지 아닌지 판별할 때, 결국 양 끝 두 글자씩만 비교해주면 된다.

 

예를 들면, "asbdasgaasdgasa"이어도, "a...xxx...a"가 같으면 양 끝 글자를 제외하고 가운데 문자열이 팰린드롬인지 판별하면 된다.

 

이를 재귀 함수로 나타내면 다음과 같이 작성할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
bool is_palindrome(string str, int start, int end) {
    
    // 기저 사건 : 팰린드롬 판별이 끝난 경우
    if (start >= end) {
        return true;
    }
 
    // 만약 비교하는 두 글자가 다른 경우 false
    if (str[start] != str[end]) {
        return false;
    }
 
    // 양 옆의 글자 빼고 비교
    return is_palindrome(str, start+1, end-1);
}
 
int main() {
 
    cout << boolalpha;
    cout << is_palindrome("racecar", 0, 6) << endl; // true
    cout << is_palindrome("notpalindrome", 0, 13) << endl; // false
    cout << is_palindrome("a", 0, 0) << endl; // true
 
    return 0;
}

 

함수 인자로 end에는 (문자열 길이 - 1)을 넣어주면 된다. 

 

이 방법은 팰린드롬 생성이나 팰린드롬과 관련된 다이나믹 프로그래밍 등에 활용되는 방법이다.

 

5. 팰린드롬 판별 - 시간 복잡도

팰린드롬을 판별할 때 네 방법 모두 모든 글자를 한 번씩 검사하므로 시간 복잡도는 $O(n)$이라고 이야기할 수 있다. 공간 복잡도는 추가적인 공간을 필요로 하지 않으니 네 방법 모두 $O(1)$이라 할 수 있다.

 

도움이 되었다면 지나가는 길에 하트 하나 눌러주세요, 양질의 글을 쓰는데 하나의 동기부여가 됩니다😍

지적이나 오타 수정 댓글 환영합니다!!