[Node.js] 백준 1254 - 팰린드롬 만들기

들어가기 전에

팰린드롬 == “회문”

거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열

e.g. : eye

이해

문자열이 주어지면, S 뒤에만 문자를 추가해서 가장 짧은 팰린드롬을 만들자

S = “abacaba”는 이미 팰린드롬이니 추가할 필요 없음. 길이 7이 최소가 된다.

S = “abab”는 abab 뒤에 a를 추가하면 ababa가 되어 팰린드롬이 되고, 길이는 5가 된다.

조건상 이게 가장 짧은 팰린드롬의 길이.

접근

틀렸던 접근

양쪽에서 들어오면서 일치하지 않으면, 그냥 바로바로 뒤에 추가하자 -> 가장 짧은걸 보장하지 않을 것 같음…

아무튼 구현해보니까 안되는 이슈 발생

제대로 된 접근

주어진 문자열 S의 뒤에서 부터 팰린드롬을 이루는 가장 긴 “부분”을 찾는 것

=> 그 이후에는, 해당 부분에 해당하지 않는 길이 만큼을 추가하면 팰린드롬이 된다!

즉

문자열 S에서 맨 앞 글자를 하나씩 제거하면서 남은 뒷부분이 팰린드롬이 되는지 확인한다.

코드

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim();

const ans = input.length;

// 팰린드롬을 판별
function isPalindrome(str) {
  const reversedStr = str.split("").reverse().join(""); // 문자열 뒤집기
  return str === reversedStr;
}

// input 문자열의 각 '접미사'가 팰린드롬인지 확인
for (let i = 0; i < input.length; i++) {
  // input.substring(i)는 input의 i번째 인덱스부터 끝까지의 부분 문자열
  if (isPalindrome(input.substring(i))) {
    // 팰린드롬이라면,
    // 원래 문자열 길이 + 팰린드롬이 아닌 앞부분의 길이 i
    console.log(ans + i);
    break;
  }
}

결론

아…

구현 자체는 어렵지 않았지만 생각하는 과정이 너무 어려웠다

왜 다들 팰린드롬을 이렇게 좋아하지?