문제
https://www.acmicpc.net/problem/9177
문제해설
n개의 데이터셋이 주어진다.
각 데이터에는 문자열 3개가 들어있다.
첫번째와 두번째 문자열을 섞어 세번째 문자열을 만들 수 있는지 판별하면 된다.
섞는 방법은 두 문자열을 합치며 각각 문자열의 순서는 바뀌면 안된다.
문제의 예시를 보면
cat과 tree를 이용해 tcraete는 만들 수 있지만
cttaree는 만들 수 없다.
만들 수 있는 문자열이면 yes를 그렇지 않다면 no를 출력해주면 된다.
문제풀이
dfs를 이용해서 해결했다.
문제를 고민해보니 백트래킹을 이용해야겠다는 생각이 들었다.
1
2
3
4
if (a[a_idx] == res[len])
dfs(a_idx + 1, b_idx, len + 1);
if (b[b_idx] == res[len])
dfs(a_idx, b_idx + 1, len + 1);
위 코드처럼 조건을 만족한다면 인덱스를 증가시키며 재귀함수를 호출하고
그렇게 증가한 길이가 세번째 문자열의 길이와 같아진다면 yes라고 판단해주었다.
하지만 재귀로만 짰을 때 시간초과가 생겼다.
왜 그런지 찾아보니 세번째 문자열에 첫번째와 두번째에 포함되지않는
새로운 문자가 들어올 수 있어 그 경우에 시간이 많이 소요되는 것으로 보였다.
그래서 test()라는 함수를 만들어
포함되지 않는 새로운 문자열이 있거나 길이가 다르다면
바로 no를 출력할 수 있게 만들어 주었더니 맞았다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
string a, b, res;
bool find_flag;
int aLen, bLen, resLen;
bool test() {
vector<int>alp(27, 0);
for (int i = 0; i < aLen; i++)
alp[a[i] - 'a']++;
for (int i = 0; i < bLen; i++)
alp[b[i] - 'a']++;
for (int i = 0; i < resLen; i++)
alp[res[i] - 'a']--;
bool flag = false;
for (int i = 0; i < 26; i++) {
if (alp[i] != 0)
flag = true;
}
if (flag)
return false;
else
return true;
}
void dfs(int a_idx, int b_idx, int len) {
if (find_flag)
return;
if (len == resLen) {
find_flag = true;
return;
}
if (a[a_idx] == res[len])
dfs(a_idx + 1, b_idx, len + 1);
if (b[b_idx] == res[len])
dfs(a_idx, b_idx + 1, len + 1);
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a >> b >> res;
find_flag = false;
aLen = a.length(); bLen = b.length();
resLen = res.length();
cout << "Data set " << i << ": ";
if (test())
dfs(0, 0, 0);
if (find_flag)
cout << "yes\n";
else
cout << "no\n";
}
return 0;
}