[백준] 1259번 - 팰린드롬수

문제 링크 : https://www.acmicpc.net/problem/1259

문제 탐색하기

1) 문제 분석

목표 : 입력한 수의 펠린드롬수 여부를 구하기
펠린드롬수 : 수의 숫자들을 뒤에서부터 읽어도 같은 수
예 : 121, 12421
무의미한 0이 앞에 올 수 없다고 가정.

2) 가능한 시간복잡도

(1) 입력 처리

0을 입력할 때까지 입력을 받음. -> O(N)

(2) 입력 순회

입력한 줄마다 한 번씩 펠린드롬수 검사 작업 -> O(N)

(3) 펠린드롬 체크

문자열 길이가 고정된 상수 -> O(1)

(4) 전체 시간복잡도

입력 처리 : O(N)
입력 순회 : O(N)
펠린드롬 체크 : O(1)
총합 : O(N) + O(N) + O(N) = O(N)

3) 알고리즘 선택 이유

입력 데이터가 적고, 문제 요구사항이 "앞뒤 비교"로 단순하기에, 인덱스를 활용한 문자열 대칭 비교 알고리즘을 선택하는 것이 최적이다.
추가적인 최적화가 필요 없는 간단 명료한 문제 구조이기 때문에, 복잡한 알고리즘 보다는 단순한 반복문 기반의 풀이가 가장 적절하다.

코드 설계하기

1. 실행 구조

1) 입력 처리

입력받은 데이터를 줄바꿈을 기준으로 나눠서 배열로 저장한다.

2) 입력 순회

입력받은 데이터를 순회하며, 펠린드롬수를 체크한다.

3) 펠린드롬수 확인

입력한 수의 절반까지 반복하며, 양끝의 인덱스를 순차적으로 비교하여 펠린드롬수 여부를 확인한다.

4) 결과 출력

펠린드롬수 여부를 출력한다.

2. 고민이 되었던 부분

JavaScript

const fs = require('fs');

// 입력을 읽어옴 (표준 입력 전체를 읽어 문자열로 만들고, 줄 단위로 나눔)
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

// 팰린드롬 판별 함수
function getIsPalindrome(num) {
    let length = num.length; // 문자열의 길이
    let half = Math.floor(Number(length) / 2); // 절반까지 비교하면 충분
    for (let i = 0; i < half; i++) {
        // 양 끝에서 점점 가운데로 비교
        if (num[i] !== num[length - 1]) {
            return "no"; // 하나라도 다르면 팰린드롬 아님
        }
        length--; // 오른쪽 인덱스를 줄이는 방식 (비권장)
    }
    return "yes"; // 모든 비교가 통과되면 팰린드롬
}

// 무한 반복문으로 입력 줄을 하나씩 꺼냄
while (1) {
    const num = input[0]; // 첫 번째 줄을 꺼냄
    input.shift(); // 첫 줄 제거 (shift는 O(N)이라 비효율적)

    if (num === '0') { // '0'이 입력되면 종료
        break;
    } else {
        console.log(getIsPalindrome(num)); // 팰린드롬 여부 출력
    }
}

: 기존 코드에서 최적화할 수 있는 부분이 무엇이 있을지 궁금하며 ChatGPT를 통해 피드백을 받은 결과 아래의 피드백을 받게 되었다.

1) getIsPalindrome 함수의 비효율적인 인덱스 조작

JavaScript

for (let i = 0; i < half; i++) {
    if (num[i] !== num[length - 1]) {
        return "no";
    }
    length--;
}

length--를 사용하여 반대쪽 인덱스를 접근하는 방식인데, 조금 비직관적이다.
가독성을 위해서 num[length-1-i] 형태로 반대쪽 인덱스를 접근하는 게 더 명확하다.

2) input.shift()의 사용

JavaScript

const num = input[0];
input.shift();

shift()는 O(N)의 비용이 걸리는 비효율적인 메소드이다.
그냥 인덱스를 이용해서 순회하는 게 더 좋다.

정답 코드

JavaScript

// 사용 언어 : Javascript

const fs = require('fs');

// 입력 전체를 읽어와 줄 단위로 나눔
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

// 팰린드롬 판별 함수
function getIsPalindrome(num) {
    const length = num.length; // 문자열 길이 저장
    const half = Math.floor(length / 2); // 절반까지만 비교하면 충분함
    for (let i = 0; i < half; i++) {
        // 양쪽 끝에서 안쪽으로 비교
        if (num[i] !== num[length - 1 - i]) {
            return "no"; // 하나라도 다르면 팰린드롬 아님
        }
    }
    return "yes"; // 모든 비교가 통과되면 팰린드롬
}

// 입력 줄 전체를 순회
for (let i = 0; i < input.length; i++) {
    const num = input[i]; // 현재 숫자 문자열
    if (num === '0') break; // 0이면 종료
    console.log(getIsPalindrome(num)); // 팰린드롬 여부 출력
}

마무리하며

처음 문제를 접했을 때는 단순히 앞뒤가 같은지만 확인하면 되는 쉬운 문제처럼 보였지만, 코드를 작성하고 개선해보면서 작은 차이가 코드의 가독성과 효율성에 얼마나 큰 영향을 미치는지 느꼈다. 특히, shift()와 같이 무심코 사용하는 메서드 하나가 전체 성능을 좌우할 수 있다는 점에서, 입력 처리와 반복문 구조를 설계하는 사고력이 중요하다는 것을 다시 깨닫게 되었다.

이번 문제를 통해, 단순한 문제일수록 가장 직관적이면서도 효율적인 방법으로 풀어내는 연습이 필요하다는 점을 다시 한 번 느낄 수 있었다.

앞으로도 작은 코드 한 줄을 설계할 때 “이게 정말 최선인가?“를 고민하는 습관을 계속 가져가야겠다.

최근 글