BOJ - 회문

BOJ - 회문

Link

https://www.acmicpc.net/problem/17609

접근방법

• 그냥 단순한 회문만 확인하는게 아니라 “유사회문”에 해당하는지도 검사해야한다.
• 유사회문은 회문이 성립하지 않는 단어에서 어떤 문자를 지우면 회문이 성립하는 단어이다.
• 그런데 회문은 그 자체로 중간 문자에 대해 “대칭성”을 갖기 때문에, 다음과 같은 접근 방법을 생각해볼 수 있다.
  • 어떤 단어에 대해, 우선 회문인지 검사한다. (회문 성립 시 0(회문) 출력)
  • 회문이 아니라면, 해당 단어를 이루는 문자를 순차 탐색하면서 하나씩 지우고, 대칭되는 문자도 지운 다음에 회문인지 확인해본다. 만약 이 과정에서 회문임을 발견하면 1(유사회문)을 출력한다.
  • 끝까지 탐색할때까지 회문임이 판별되지 않으면 2(회문, 유사회문 아님)를 출력한다.

Code

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

const isPalindrome = (word) => {
  return word == word.split("").reverse().join("");
};

let words = Number(input[0]);

for (let w = 1; w <= words; w++) {
  let word = input[w];
  if (isPalindrome(word)) {
    console.log(0);
  } else {
    let found = false;
    let wordLength = word.length;

    for (let i = 0; i < parseInt(wordLength / 2); i++) {
      if (word[i] != word[wordLength - i - 1]) {
        if (isPalindrome(word.slice(0, i) + word.slice(i + 1, wordLength))) {
          found = true;
        }
        if (
          isPalindrome(
            word.slice(0, wordLength - i - 1) +
              word.slice(wordLength - i, wordLength)
          )
        ) {
          found = true;
        }
        break;
      }
    }
    if (found) {
      console.log(1);
    } else {
      console.log(2);
    }
  }
}