회문

문제

언어

  • JavaScript

순서도

  1. 각 테스트 케이스에 대해서
  2. 팰린드롬인지 검사
  3. 팰린드롬이 아니라면 유사 팰린드롬인지 검사
    • 유사 팰린드롬인지 검사는 문자를 하나 삭제하고, 삭제한 문자열에 대해서 팰린드롬인지 검사
  4. 각 경우에 맞게 출력

문제 풀이 step 1

  • 회문 또는 팰린드롬은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말합니다.
  • 본 문제에서는 총 3 가지 경우가 소개됩니다.
    • 회문인 경우
    • 유사 회문인 경우 (회문은 아니지만 문자열에서 문자 하나를 삭제하면 회문으로 만들 수 있는 문자열)
    • 회문도 유사 회문도 아닌 경우
  • 각 테스트 케이스에 대해서 회문인지 유사 회문인지 둘다 아닌지 판별하는 문제입니다.

문제 풀이 step 2

  • 우선, 주어진 문자열이 회문인지 확인합니다.
    • 회문인지 검사하는 로직은
    • 두 개의 포인터를 생성합니다. 한 포인터는 문자열의 가장 왼쪽을 가리키고, 한 포인터는 문자열의 가장 오른쪽을 가리킵니다.
    • 두 개의 포인터가 서로를 향해서 한 칸씩 이동하며, 서로 가리키는 문자가 모두 같다면, 회문입니다.
    • 반면에, 서로 가리키는 문자가 다르다면, 회문이 아닙니다.
  • 만약 회문이라면, 0 을 출력하고, 회문이 아니라면, 유사 회문인지 검사합니다.
    • 유사 회문인지 검사하는 로직은
    • 회문인지 검사하는 로직과 마찬가지로 두 개의 포인터가 서로를 향해서 한 칸씩 이동합니다.
    • 도중에 두 개의 포인터가 서로 가리키는 문자가 다르다면, 두 번의 검사를 진행합니다.
      • 한 번은 왼쪽 포인터를 한 칸 오른쪽으로 이동한 다음에 이 상태에서 회문인지 검사합니다.
      • 다른 한 번은 오른쪽 포인터를 한 칸 왼쪽으로 이동한 다음에 이 상태에서 회문인지 검사합니다.
      • 이 두 번의 검사 중에서 한 번의 검사라도 회문이라면 이는 유사 회문입니다.
      • 만약 두 번의 검사 모두 회문이 아니라면 이는 회문도 유사 회문도 아닌 경우입니다.
  • 검사 결과에 따라서 유사 회문이면 1 을, 회문도 유사 회문도 아니라면 2 를 출력합니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 꼭 다시 풀어볼 문제입니다.
  • 팰린드롬 문제는 이상하게 쉽게 푼 경험이 없는 것 같습니다. 이번에도 많은 시행 착오를 겪었는데, 결국 제 로직대로는 풀리지가 않았습니다.
  • 그리고 재귀를 사용하는 것이 로직 상으로는 간결하고, 명료한 것 같습니다.

소스 코드

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

// 회문인지 검사하는 함수
const checkPalindrome = (str, left, right) => {
	while (left <= right) {
		if (str[left] !== str[right]) return false;
		left += 1;
		right -= 1;
	}

	return true;
};

// 유사 회문인지 검사하는 함수
const checkPseudoPalindrome = (str, left, right) => {
	while (left <= right) {
		// 서로가 가리키는 문자가 다른 경우
		if (str[left] !== str[right]) {
			// 두 번의 회문 검사
			// 한 번의 검사라도 true 면 유사 회문
			// 두 번의 검사 모두 false 면 회문도 유사 회문도 아님
			return (
				checkPalindrome(str, left + 1, right) === true ||
				checkPalindrome(str, left, right - 1) === true
			);
		}

		left += 1;
		right -= 1;
	}

	return true;
};

const solution = (input) => {
	let t = Number(input[0]);

	let res = "";
	let index = 1;
	while (t-- > 0) {
		const str = input[index++];

		const [left, right] = [0, str.length - 1];
		if (checkPalindrome(str, left, right)) {
			// 회문인 경우
			res += "0\n";
			continue;
		}

		if (checkPseudoPalindrome(str, left, right)) {
			// 유사 회문인 경우
			res += "1\n";
		} else {
			// 회문도 유사 회문도 아닌 경우
			res += "2\n";
		}
	}

	return res;
};

console.log(solution(input));