[JS] 12919_A와 B 2

문제

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

 

풀이

이 문제의 경우 S 문자열 부터 T 까지 구하는것 보다, T에서 하나씩 소거하며 경우의 수를 찾는것이 더 로직을 설계하는데에 이점이 있다고 판단했다.

 

이러한 방법을 이용해 두 가지 로직을 구현했다.

1. 맨 뒤의 A가 있다면 맨 뒤의 A를 없애고 재귀 동작을 진행
2. 맨 앞에 B가 있다면 역순으로 바꾸고 맨 뒤에 있는 B를 제거하고 재귀 동작을 진행

2번 동작에서 맨 앞의 B를 먼저 제거하지 않는 것은 문자열이 길어질 수록 JS의 shift() 메서드를 사용하면 시간 복잡도가 미세하나마 증가할 것을 우려, 완전탐색을 진행하는 메서드를 줄이기 위해 reverse() 메서드 적용뒤 pop()하여 기능을 구현했다.

 

 

코드

const input = require("fs")
  .readFileSync(
    process.platform === "linux" ? "/dev/stdin" : __dirname + "/example.txt"
  )
  .toString()
  .trim()
  .split("\n")
  .map((e) => e.trim());

const s = input.shift();
const t = input.shift().split("");
let answer = 0;

// Top -> Bottom
const check = (arr, len) => {
  if (len === s.length) {
    if (arr.join("") === s) answer = 1;
    return;
  } else {
    if (arr[len - 1] === "A") {
      const newArr = [...arr];
      newArr.pop();
      check(newArr, len - 1);
    }
    if (arr[0] === "B") {
      const newArr = [...arr].reverse();
      newArr.pop();
      check(newArr, len - 1);
    }
  }
};
check(t, t.length);
console.log(answer);

// 실패한 코드
// 완전 탐색을 통해 진행하려 했다... Bottom -> Top
// let flag = false;
// const a = (st) => {
//   if (flag || st.length === t.length) {
//     if (st === t) flag = true;
//     return;
//   }
//   a(st + 'A');
//   b(st + 'A');
// }

// const b = (st) => {
//   if (flag || st.length === t.length) {
//     if (st === t) flag = true;
//     return;
//   }
//   const newSt = 'B' + st.split('').reverse().join('');
//   a(newSt);
//   b(newSt);
// }

// a(s);
// b(s);

// console.log(flag ? 1 : 0);