[Algorithm] C++ 뒤집어도 같은 숫자(palindrome) 판별하기

123454321, 46864와 같이 뒤집어도 같은 것을 palindrome이라 합니다. 이런 palindrome을 판별하기 위한 최적의 알고리즘에 대해 고찰해 보겠습니다.

 

 

간단히 바로 생각나는 알고리즘은

1. 숫자를 문자열로 바꾼다.
2. 문자열을 뒤집는다.
3. 두 문자열을 비교한다.

bool is_palindrome(const string & str){
    auto copy = str;
    std::reverse(copy.begin(), copy.end());
    return copy == str;
}

bool is_palindrome_str(int data){
    return is_palindrome(std::to_string(data));
}

int main(int argc, const char * argv[]) {
    vector<int> data = { 987654, 1234321, 456789, 102979201 };
    for(int i=0;i<data.size();i++){
        cout << data[i];
        if(is_palindrome_str(data[i])){
            cout << " is palindrome";
        } else {
            cout << " is NOT palindrome";
        }
        cout << endl;
    }
}

OUTPUT:
987654 is NOT palindrome
1234321 is palindrome
456789 is NOT palindrome
102979201 is palindrome

PEFORMANCE (1,000 times for 1234321) :  113 milliseconds

이 코드의 문제점은 무거운 memory allocation과 swap이 일어난다는것이고 1만번만 반복해도 1초라는 어마어마한 퍼포먼스를 사용하는 아주 안좋은 알고리즘 되겠다.

 

memory access를 최대한 줄이고 시간복잡도도 1/2로 줄여보자

 

알고리즘

1. 왼쪽부터 1씩 증가하는 i번째 문자와 오른쪽 부터 1씩 감소하는 j번째 문자와 비교한다.
2. 만약 다르다면 false를 리턴한다.
3. i >= j 같다면 true을 리턴한다.

bool is_palindrome(const string & str){
    for(size_t i=0,j=str.length()-1; i < j; i++, j--){
        if(str[i] != str[j])
            return false;
    }
    return true;
}

 

OUTPUT:
987654 is NOT palindrome
1234321 is palindrome
456789 is NOT palindrome
102979201 is palindrome

PEFORMANCE (1,000 times for 1234321) :  81 milliseconds

memory allocation과 swap을 제거하여 상당부분 퍼포먼스를 개선하였다. Search도 딱 N/2만 한다.

그래도 string전환으로인한 memory access문제의 개선은 불가하다.

 

input이 숫자라는 단서에 착안하여 memory access자체를 제거해 보자

 

알고리즘

1. reverse 변수를 0으로 초기화
2. reverse 변수에 10을 곱해준다. ( 왼쪽으로 이동 )
3. reverse 변수 입력값을 10으로 나눈 나머지를 더해준다. (마지막 숫자)
4. 입력값을 10으로 나눠서 저장한다. ( 마지막 숫자 제거 )
5. 입력값이 0이면 중단하고 아니라면 2번을 반복한다.

int reverse(int data){
    int reverse = 0;
    while(data > 0){
        reverse *= 10;
        reverse += data % 10;
        data /= 10;
    }
    return reverse;
}

bool is_palindrome(int data){
    return reverse(data) == data;
}

OUTPUT:
987654 is NOT palindrome
1234321 is palindrome
456789 is NOT palindrome
102979201 is palindrome

PEFORMANCE (1,000 times for 1234321) :  16 milliseconds

1번 예제에 비하여 1/10로 실행시간이 줄었다. 이유는 compiler는 계속된 연산이기 때문에 memory 접근을 최소화하고 register단에서 연산을 마무리하기 때문에 상당히 빠르다.