https://www.acmicpc.net/problem/12919
12919호: A와 B 2
수빈은 A와 B로만 이루어진 영어 단어가 있다는 사실에 놀랐다. AB(Abdominal), BAA(Crying Sheep), AA(Art Lava), ABBA(Swedish pop group) 등이 대표적이다. 이 사실에 놀란 수빈
www.acmicpc.net
수빈은 A와 B로만 이루어진 영어 단어가 있다는 사실에 놀랐다. AB(Abdominal), BAA(Crying Sheep), AA(Art Lava), ABBA(Swedish pop group) 등이 대표적이다.
이 사실에 놀란 수빈은 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어지면 이 게임은 S를 T로 변환합니다. 문자열을 변경할 때 두 가지 작업만 가능합니다.
- 문자열 끝에 A를 추가합니다.
- 문자열 끝에 B를 추가하고 문자열을 뒤집습니다.
주어진 조건에서 S가 T가 될 수 있는지 알아보는 프로그램을 작성하십시오.
기입
S는 첫 번째 줄에, T는 두 번째 줄에 제공됩니다. (1 ≤ S 길이 ≤ 49, 2 ≤ T 길이 ≤ 50, S 길이 < T 길이)
누르다
S를 T로 변환할 수 있으면 1을 반환하고 그렇지 않으면 0을 반환합니다.
예시 입력 1
A
BABA
예제 출력 1
1
해결하다
- 재귀를 사용하여 모든 경우를 확인하고 기본 사례를 s와 t의 길이로 설정했습니다.
- 주어진 경우가 성공하면 응답 배열에 저장되고 응답에 t가 포함되어 있으면 1을, 그렇지 않으면 0을 반환합니다.
문제
- 재귀 함수에서 문자열 s가 target에 없는 경우와 inverse s가 target에 없는 경우를 반환하지 않으면 불필요한 계산과 타임아웃이 발생한 것이다.
암호
const (s,t) = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
// 일단 길이가 맞아야함 => base case
const answer = ();
const solution = (s, target) => {
if(!target.includes(s) && !target.includes((...s).reverse().join(''))) return;
if(s.length === target.length) {
return answer.push(s);
}
solution(s + "A", target);
solution((...s+"B").reverse().join(''), target)
}
solution(s, t);
console.log(answer.includes