BOJ - 회문

문제

BOJ — 회문

접근 방법

회문이면 0, 문자 하나를 삭제해서 회문이 되는 유사회문이면 1, 둘 다 아니면 2를 출력한다.

양 끝에 포인터를 두고 같은 문자인 동안 안쪽으로 이동한다. 끝까지 불일치가 없으면 회문이다.

처음으로 문자가 다른 위치를 left, right라고 하면 다음 두 경우만 검사하면 된다.

1. 왼쪽 문자 하나를 제외한 구간 [left + 1, right]가 회문인지 확인한다.
2. 오른쪽 문자 하나를 제외한 구간 [left, right - 1]가 회문인지 확인한다.

두 문자를 동시에 삭제하는 것이 아니다. 양쪽 문자가 다르면 삭제 한 번으로 회문을 만들기 위해 둘 중 하나를 제외해야 한다. 그 전에 일치한 바깥 구간은 그대로 유지할 수 있다. 두 검사 중 하나라도 성공하면 유사회문이다.

부분 문자열이나 뒤집은 배열을 만들지 않고 인덱스로 비교하면 문자열 길이에 비례한 임시 메모리 할당을 줄일 수 있다. 입력은 공백 단위로 나누어 줄 끝의 \r도 제거한다.

코드

const fs = require('fs')
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/)
const count = Number(input[0])

function isPalindrome(word, left, right) {
  while (left < right) {
    if (word[left] !== word[right]) return false
    left += 1
    right -= 1
  }
  return true
}

function classify(word) {
  let left = 0
  let right = word.length - 1
  while (left < right) {
    if (word[left] !== word[right]) {
      return isPalindrome(word, left + 1, right) ||
        isPalindrome(word, left, right - 1)
        ? 1
        : 2
    }
    left += 1
    right -= 1
  }
  return 0
}

const answer = []
for (let i = 1; i <= count; i++) {
  answer.push(classify(input[i]))
}
console.log(answer.join('\n'))

복잡도와 경계 조건

문자열 길이가 n이면 한 문자열의 판별 시간은 O(n), 판별 함수의 추가 공간은 O(1)이다. 입력과 출력 저장 공간은 별도다.

왼쪽 삭제만 가능한 경우와 오른쪽 삭제만 가능한 경우를 모두 확인한다. 첫 불일치 이후의 구간 검사에서는 추가 삭제를 허용하지 않는다.