[백준/C++] 1259번: 팰린드롬수 - 투 포인터와 인덱스 조건의 중요성

1. 문제 정보

• 문제 번호: 1259번
• 문제 이름: 팰린드롬수
• 사용 언어: C++
• 문제 링크: 백준 1259번 바로가기
• 문제 요약: 앞뒤가 똑같은 단어(팰린드롬)인지 판별하는 문제. 'yes' 또는 'no'를 출력하며, 입력이 '0'이면 종료한다.
  
  
  
  

2. 시행착오 (실패한 접근)

처음에는 단순히 "가운데를 기준으로 양옆으로 뻗어나가며 비교하자"라고 생각했다. 그래서 문자열 길이가 짝수일 때와 홀수일 때를 나누어 middle 인덱스를 구하고, 반복문을 돌렸다.

❌ 실패한 코드 (Index Out of Bounds)

 

// 짝수일 경우
int middle1 = size/2 - 1;
// ...
// 문제의 반복문 조건: i가 커지면 middle1 - i가 음수가 됨
for(int i=0; i + middle1 < size; i++){ 
    if(number[middle1 - i] != number[middle2 + i]){ ... }
}

 

[문제점 분석]

• 조건문을 i가 커지는 것(size 기준)만 신경 쓰고, 작아지는 쪽(0 기준)을 신경 쓰지 않았다.
• 배열의 시작은 항상 0부터 시작이라는 것을 고려하지 않았다.
• 예를 들어 "1221"의 경우, 반복문이 끝까지 돌면서 number[-1]을 참조하게 되어 에러가 발생했다.
• 교훈: 배열 인덱스를 다룰 때는 상한선(size)뿐만 아니라 하한선(0)도 반드시 체크해야 한다.

3. 해결 방법 (투 포인터 & 문자열 누적)

복잡하게 짝수/홀수를 나누고 가운데서 시작하는 대신, 양 끝에서 시작해서 가운데로 모이는 방식(Two Pointers)으로 로직을 변경했다.

핵심 아이디어

1. j는 맨 앞(0), k는 맨 뒤(size-1)에서 시작한다.
2. number[j]와 number[k]를 각각 reader1, reader2 문자열에 저장한다.
3. 두 포인터가 서로 만나거나 교차할 때(j==k 혹은 j+1==k)까지 반복한다.
4. 만들어진 두 문자열이 같은지 비교한다.

 

 

4. 정답 코드 (C++)

 

#include <iostream>
#include <vector>
#include <string> // string 사용

using namespace std;

int main() {
    while(true){
        string number;
        cin >> number;
        
        if(number == "0"){
            break;
        }

        int size = number.size();
        string reader1 = ""; // 앞->뒤로 읽은 값 저장
        string reader2 = ""; // 뒤->앞으로 읽은 값 저장 (실제로는 뒤쪽 문자를 순서대로 저장)
        
        int j = 0;
        int k = size - 1;

        while(true){
            reader1 += number[j];
            reader2 += number[k];

            // [종료 조건]
            // 홀수 길이: 정확히 가운데서 만남 (예: 1 2 1 에서 2)
            if(j == k){ 
                break;
            }
            // 짝수 길이: 서로 교차하기 직전에 만남 (예: 1 2 2 1 에서 2와 2)
            else if(j + 1 == k){ 
                break;
            }
            else { 
                // 아직 안 만났으면 포인터 이동
                j++;
                k--;
            }
        }

        if(reader1 == reader2){
            cout << "yes" << endl;
        }
        else{
            cout << "no" << endl;
        }
    }
    return 0;
}

 

 

5. 배운 점 & 회고 (TIL)

A. 조건문과 실행 순서의 중요성 (Logic Flow)

코드를 수정하면서 if(j!=k) 다음에 j++, k--를 하고 종료 조건을 검사했더니, 마지막 글자를 제대로 체크하지 못하거나 루프를 한 번 더 도는 문제가 있었다.

• "값을 처리(저장/비교)하고 -> 종료 조건을 확인하고 -> 인덱스를 이동한다(++,--)"는 순서를 명확히 해야 한다.

B. 짝수와 홀수 케이스 (Edge Case)

투 포인터가 만나는 지점이 짝수 길이일 때(j+1==k)와 홀수 길이일 때(j==k) 다르다는 점을 if-else로 정확히 처리해야 한다. 이 조건을 놓치면 무한 루프에 빠지거나 엉뚱한 값을 비교하게 된다.

C. 더 간단한 방법은 없을까? (Optimization)

문제를 풀고 나서 생각해 보니, 굳이 reader 문자열을 만들지 않고 그때그때 비교만 해도 된다.

// 최적화 팁: 문자열을 계속 더하는 것보다 비교만 하는 게 더 빠름
bool isPalindrome = true;
for(int i = 0; i < size / 2; i++) {
    if(number[i] != number[size - 1 - i]) {
        isPalindrome = false;
        break;
    }
}

다음에는 이렇게 더 직관적이고 메모리를 덜 쓰는 방식으로도 구현해 봐야겠다.

 

결론

"인덱스는 항상 범위를 벗어날 수 있다는 공포감을 가지고 코딩하자."