백준 / 재귀 / 12919번 / A와 B 2 / JS

문제 간단설명

문자열 S와 T가 주어진다.

S는 다음 두가지 방법으로만 T를 만들어야 한다.

• 문자열의 뒤에 A를 추가한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

만약 S를 T로 만들 수 있으면 1, 아니라면 0을 출력하는 문제이다.

 

제한 사항

• 1 <= S의 길이 <= 49
• 2 <= T의 길이 <= 50
• S의 길이 < T의 길이

 

실패 코드 (시간 초과)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

const [S, T] = input.map((el) => el.trim());

const IMPOSSIBLE = 0;
const POSSIBLE = 1;

let result = 0;

function solution() {
  makeString([...S]);

  console.log(result);
}

function makeString(current) {
  if (current.length === T.length) {
    if (current.join('') === T) {
      result = 1;
    }

    return;
  }

  makeString([...current, 'A']);
  makeString([...current, 'B'].reverse());
}

solution();

 

위 코드는 문제를 그대로 구현한 코드인데, 시간초과가 났다.

주어진 범위내에서 S가 극단적으로 짧고, T가 극단적으로 길다면 길이를 하나씩 늘려갈때마다 두 가지 경우의 수를 모두 해보는 방법이기 때문에 시간이 오래걸려서 시간초과가 났다.

 

성공 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

const [S, T] = input.map((el) => el.trim());

const IMPOSSIBLE = 0;
const POSSIBLE = 1;

let result = IMPOSSIBLE;

function solution() {
  makeS(T);

  console.log(result);
}

function makeS(current) {
  if (current.length === S.length) {
    if (current === S) {
      result = POSSIBLE;
    }
    return;
  }

  if (current.endsWith('A')) {
    makeS(current.slice(0, -1));
  }
  if (current.startsWith('B')) {
    makeS([...current].reverse().slice(0, -1).join(''));
  }
}

solution();

 

실패한 방법처럼 S를 T로 만드는것이 아닌, T를 S로 만들면 된다.

그럼 단순히 역으로 생각해서 끝에 A가 온 경우엔 A만 지우면 되고, 처음이 B로 시작하는 경우엔 뒤집고 B를 지우면 된다.

그렇게 하면 모든 경우의 수를 고려할 필요는 없다.