문제 개요

문제: 회문

분류: 문자열, 두 포인터

난이도: 골드5

문제 풀이

왼쪽 끝, 오른쪽 끝에 각각 포인터를 두고 동시에 중간으로 한 칸씩 이동하며 서로 다른 문자가 있는지 확인한다.

• 서로 다른 문자가 있다면
  • 이미 회문은 아니고, 유사회문이거나 아니거나 둘 중 하나다.
  • 왼쪽이나 오른쪽 포인터 중 하나만 안쪽으로 한 칸 옮기고 재탐색한다.
    • 서로 다른 문자가 또 발견된다면 유사회문이 아니므로 0을 출력한다.
    • 서로 다른 문자가 없다면 유사회문이므로 1을 출력한다.
• 서로 다른 문자가 없다면
  • 모든 문자가 같다는 의미, 즉 회문이므로 2를 출력한다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const [T, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");

const checkPseudoPalindrome = (str, left, right) => {
  // 포인터를 옮겨서 다시 탐색한다.
  while (left < right) {
    // 서로 다른 문자가 하나라도 있다면 유사회문이 아니다.
    if (str[left] !== str[right]) return false;
    left++;
    right--;
  }
  // 모든 문자가 같다면 유사회문이다.
  return true;
};

const getPalindromeNumber = (str) => {
  let left = 0;
  let right = str.length - 1;

  while (left < right) {
    if (str[left] !== str[right]) {
      // 서로 다른 문자가 있다면 이미 회문은 아니고, 유사회문이거나 아니거나 둘 중 하나다.
      // 1. 왼쪽 포인터를 오른쪽으로 한 칸 옮기거나
      // 2. 오른쪽 포인터를 왼쪽으로 한 칸 옮겨서
      // 다시 탐색했을 때 둘 중 한 경우라도 서로 다른 문자가 없다면 유사회문이므로 1 반환
      // 그렇지 않다면 유사회문이 아니므로 2 반환
      if (
        checkPseudoPalindrome(str, left, right - 1) ||
        checkPseudoPalindrome(str, left + 1, right)
      )
        return 1;
      else return 2;
    }
    left++; 
    right--;
  }
  // 모든 문자가 같다면 회문이므로 0 반환
  return 0;
};

const solution = () => {
  const answer = [];

  input.forEach((str) => {
    answer.push(getPalindromeNumber(str));
  });

  console.log(answer.join("\n"));
};

solution();