[BaekJoon 1259][🟤1] 팰린드롬수

❓ 문제

백준 1259 - “팰린드롬수”

🎯 난이도

Bronze 🟤1

🧠 풀이

1. 내 풀이 (문자열)

- 알고리즘

• string

- 설명

정수를 받아서 string으로 변환하고, reverse 하는 방식의 풀이이다.

문제를 보자마자 몇번째 문자를 바꾸라는 것도 없고, 정수의 크기 자체도 크지 않아서 이 방법부터 떠올랐다. 그리고 실제로도 가장 많은 사람들이 사용한 풀이이기도 하다.

시간 복잡도는 O(N)인데, reverse의 성능이 문자 갯수에 비례하기 때문이다.

- 코드

내 풀이 코드

#include <iostream>

#include <string>

#include <algorithm>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(true)
    {
        int iInput{};
        cin >> iInput;

        if(iInput == 0)
        {
            break;
        }

        string strInput{ to_string(iInput) };   // string으로 형변환
        string strTemp(strInput);

        reverse(strInput.begin(), strInput.end());

        if(strInput == strTemp)
        {
            cout << "yes" << "\n";
        }
        else
        {
            cout << "no" << "\n";
        }
    }    

    return 0;
}

---

2. 추가 풀이 1 (투 포인터)

- 알고리즘

• Two Pointer

- 설명

투 포인터 알고리즘을 사용한 팰린드롬 문제의 가장 정석적인 풀이이다.

말이 필요 없는 팰린드롬 문제에서 가장 많이 보이는 풀이이다. reverse도 사용하지 않기 때문에 <algorithm> 라이브러리도 필요가 없다.

시간 복잡도는 문자열 길이에 비례하기 때문에 O(N)이다.

- 코드

추가 풀이 코드

#include <iostream>

#include <string>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(true)
    {
        int iInput{};
        cin >> iInput;

        
        if(iInput == 0)
        {
            break;
        }
        
        string strInput{ to_string(iInput) };
        bool bPalin{ true };        // 팰린드롬인지 실시간으로 추적하는 flag 변수

        for(int iLeft = 0, iRight = static_cast<int>(strInput.length()) - 1; iLeft < iRight; ++iLeft, --iRight)
        {
            if(strInput[iLeft] != strInput[iRight]) // 다르면 바로 break;
            {
                bPalin = false;
                break;
            }
        }

        cout << (bPalin ? "yes" : "no") << "\n";
    }    

    return 0;
}

---

3. 추가 풀이 2 (정수 연산)

- 알고리즘

• Mathematics

- 설명

string 없이 정수 연산만으로 해결하는 풀이이다.

입력이 정수형으로 들어오기 때문에, 굳이 string으로 변환하기보다 입력받은 정수를 자릿수마다 변환 연산을 통해 손수 뒤집어주는 방식이다.

방법이 독특해서 이 문제를 포스팅한 이유이기도 하다. 하지만 위의 두 풀이가 더 직관적이므로 그리 추천할만한 풀이는 아닌 듯하다.

정수 자릿수만큼 반복하므로 시간 복잡도는 O(N)이다.

- 코드

추가 풀이 코드

#include <iostream>

#include <string>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while(true)
    {
        int iInput{};
        cin >> iInput;

        
        if(iInput == 0)
        {
            break;
        }

        int iOrigin{ iInput }, iReverse{};

        // iReverse에는 iInput의 1의 자리를 더한 뒤 10을 곱하고 iInput은 10을 나눠주는 연산을 반복
        while(iInput > 0)
        {
            iReverse = iReverse * 10 + iInput % 10;
            iInput /= 10;
        }

        if(iOrigin == iReverse)
        {
            cout << "yes\n";
        }
        else
        {
            cout << "no\n";
        }
    }    

    return 0;
}

---

💭 후기

가장 기본적인 형태의 팰린드롬 문제가 아닐까 싶다.

투 포인터 알고리즘은 이러한 유형의 문제에서 정말 자주 쓰이는 알고리즘이고, 정수 변환 풀이는 “이런 풀이도 있구나” 하고 봐두면 좋을 것 같다.

🔗 참고자료

• 투 포인터 알고리즘