[백준] 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. 고민이 되었던 부분

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 함수의 비효율적인 인덱스 조작

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

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

2) input.shift()의 사용

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

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

 

 

정답 코드

// 사용 언어 : 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()와 같이 무심코 사용하는 메서드 하나가 전체 성능을 좌우할 수 있다는 점에서, 입력 처리와 반복문 구조를 설계하는 사고력이 중요하다는 것을 다시 깨닫게 되었다.

 

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

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