백준 12919 < A와 B 2 > JavaScript

📍문제 링크

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

12919번: A와 B 2

 

📍알고리즘 분류

- 구현
- 문자열
- 브루트포스 알고리즘
- 재귀

 

📍문제 풀이

- 문자열 X, Y와 연산1, 2 가 주어진다

- 연산1 : 문자열의 뒤에 A를 추가한다.

- 연산2: 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

 

오직 2가지 연산을 통해 X를 Y로 만들 수 있는지 판별한다.

 

- 이 문제를 풀 때, A 를 BABA로 만드는 것보다,

BABA를 A로 만드는 것이 더 쉽고, 직관적이고, 경우의 수가 적다.

즉, Y -> X 가능한지 확인

 

그리고 재귀를 통해 해결할 수 있다.

 

- reverse() 를 이용하기 위해 변화할 문자열을 배열로 바꾼다.

 

📍의사 코드

재귀 함수를 만든다

- base case1 : Y = X 이면 정답

- base case2 : Y의 길이가 X의 길이보다 작아지면 빈 return으로 종료

 

- 조건1 : 연산1 가능하면 수행후 재귀 호출

- 조건2 : 연산2 가능하면 수행후 재귀 호출

 

📍코드 (JavaScript)

const [in1, in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

let T = in2.split("");
const answer = [];

const track = (arr) => {
  if (arr.join("") === in1) {
    answer.push(1);
  }
  if (arr.length < in1.length) return;
  if (arr.slice(-1)[0] === "A") {
    const newArr = [...arr];
    newArr.pop();
    track(newArr);
  }
  if (arr[0] === "B") {
    const newArr = [...arr];
    newArr.shift();
    track(newArr.reverse());
  }
};

track(T);
if (answer.includes(1)) console.log(1);
else console.log(0);

 

📍리뷰

- 배열 answer에 1을 push 하고, include로 찾는 방법 대신 아예 처음에 answer = 0 선언,

정답인  base case에서 answer = 1 해주는 방법을 시도했으나, 오히려 시간 복잡도 증가

// 정답이나, 위 코드보다 시간 복잡도 8ms 느림

const [in1, in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

let T = in2.split("");
let answer = 0;

const track = (arr) => {
  if (arr.join("") === in1) {
    answer = 1;
  }
  if (arr.length < in1.length) return;
  if (arr.slice(-1)[0] === "A") {
    const newArr = [...arr];
    newArr.pop();
    track(newArr);
  }
  if (arr[0] === "B") {
    const newArr = [...arr];
    newArr.shift();
    track(newArr.reverse());
  }
};

track(T);
console.log(answer);