문제 개요

문제: A와 B 2

분류: 문자열, 브루트포스 알고리즘, 재귀

난이도: 골드5

문제 풀이

S를 T로 바꿀 수 있는지가 아니라 T를 S로 바꿀 수 있는지를 재귀함수로 확인한다.

• 현재 문자열이 S와 같다면 1을 반환
• 현재 문자열의 마지막 문자가 “A”라면 마지막 문자를 제외한 문자열에 대해 재귀함수 호출
• 현재 문자열의 첫 문자가 “B”라면 첫 문자를 제외한 뒤집힌 문자열에 대해 재귀함수 호출

각각의 호출에서 재귀함수가 반환한 값과 초기값이 0인 result 변수를 OR 연산하고 이를 반환하여 최종적으로 재귀함수가 반환하는 값을 출력한다.

코드

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

const check = (str) => {
  if (str === S) return 1;

  let result = 0;
  if (str[str.length - 1] === "A")
    result |= check(str.slice(0, str.length - 1));
  if (str[0] === "B") result |= check([...str.slice(1)].reverse().join(""));

  return result;
};

console.log(check(T));