[JavaScript] 12904. A와 B

문제 링크

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

문제 해설

A와 B로만 이루어진 영어 단어가 존재한다.

두 문자열(S, T) 가 주어질 때, S를 T로 바꿀 수 있는 지 판별한다.

문자열을 바꾸기 위한 연산은 다음과 같다.

1. 문자열의 뒤에 A를 추가한다.

2. 문자열을 뒤집고 뒤에 B를 추가한다.

 

예시

B
ABBA

 

B가 ABBA 가 되기 위해선 B, BA, ABB, ABBA 과정을 거치며, 최종적으로 ABBA가 됐으므로, 1을 리턴한다.

만약 변경하지 못할 경우, 0을 리턴한다.

 

❌ 문제 접근 1 

연산의 종류는 2가지이다. 따라서 연산 (1) 과 연산 (2)를 적용했을 때 다음과 같이 트리 형태로 나타낼 수 있다.

시간 복잡도는 O(2^N)이 될것이고, 제한조건에 N은 1000자리이하라고 나와있으니, 시간 초과이다.

 

⭕ 문제 접근

1️⃣ ABBA 직전의 문자열은 어떤것이였을까?

- ABBA : 마지막 문자가 'A' 이기 때문에 첫번째 연산을 한 결과일 것이다.

- ABB + 'A' = > ABBA

- 따라서 직전 문자열은 ABB이다.

 

2️⃣ ABB 직전의 문자열

- ABB : 마지막 문자가 'B' 이기 때문에 두번째 연산을 한 결과일 것이다.

- BA -> AB + 'B => ABB

- 따라서 직전 문자열은 AB이다.

 

전체 코드

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

const s1 = input[0];
let s2 = input[1];

let canBe = false;
while (s1.length <= s2.length) {
  if (s1 === s2) {
    canBe = true;
    break;
  }
  if (s2[s2.length - 1] === "A") {
    s2 = s2.slice(0, s2.length - 1);
  } else {
    s2 = s2.slice(0, s2.length - 1);
    s2 = s2.split("").reverse().join("");
  }
}

console.log(canBe ? 1 : 0);