수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.
이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.
주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.
가장 먼저 생각난 풀이 : S에서 조건1 또는 조건2를 선택하며 dfs방식으로 푼다. → 즉, 최악의 경우 약 40초가 걸린다 시간 초과로 실패하는 풀이.
사실 T의 뒷문자로 조건이 한 가지로 한정되는 문제이다.
ex)
- 문자열의 뒤에 A를 추가한다. → T의 뒷문자는 A가 된다.
- 문자열을 뒤집고 뒤에 B를 추가한다. → T의 뒷문자는 B가 된다.
따라서 T의 뒷문자를 보고 조건을 판단 뒤 해당 조건을 적용하기 전으로 되돌리는 것을 반복하여, S와 같은 길이가 되었을 때 만들어진 T가 동일한지 확인하면 된다.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string S, T;
int ans = 0;
int main() {
cin >> S >> T;
int s_leng = S.length();
int t_leng = T.length();
for (int j = 0; j < t_leng-s_leng; j++) {
if (T[T.length()-1] == 'B') { // 뒤집고 B를 추가한 경우.
T.erase(--T.end());
reverse(T.begin(), T.end());
}
else { // A를 추가한 경우.
T.erase(--T.end());
}
}
if (T.compare(S) == 0) {
ans = 1;
}
cout << ans;
return 0;
}
수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.
이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.
주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.
가장 먼저 생각 난 풀이 : 문자열 길이가 줄어들었지만, 이 또한 12904번 A와 B 문제처럼 dfs로 풀시 시간초과가 난다. 즉 약 2초 초과
해당 문제도 조건을 살펴보자.
ex)
- 문자열의 뒤에 A를 추가한다. → T의 뒷문자는 A가 된다. (앞문자는 A, B 모두 될 수 있다.)
- 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. → T의 앞문자는 B가 된다. (뒷문자는 A, B 모두 될 수 있다.)
따라서 T의 앞문자와, 뒷문자를 보고 조건을 판단 뒤 해당 조건을 적용하기 전으로 되돌리는것을 반복하여, S와 같은 길이가 되었을 때 만들어진 T가 동일한지 확인하면 된다. (둘 다 해당될수있으므로 두 조건을 if-else문으로 묶는일은 없도록 해야한다.)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string S, T;
int ans = 0;
void dfs(string s) {
if (s.length() <= S.length()) {
if (S.compare(s) == 0) ans = 1;
return ;
}
if (s[s.length()-1] == 'A') { // 1. A를 추가 -> A가 뒷자리
string s_temp = s;
s_temp.erase(s_temp.end()-1);
dfs(s_temp);
}
if (s[0] == 'B') { // 2. B를 추가하고 뒤집 -> B가 앞자리
string s_temp = s;
s_temp.erase(s_temp.begin());
reverse(s_temp.begin(), s_temp.end());
dfs(s_temp);
}
}
int main() {
cin >> S >> T;
dfs(T);
cout << ans;
return 0;
}