8905번: 리트
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 한 알파벳을 리트로 바꿨을 때 리트의 최대 길이 k가 주어진다. (1 ≤ k ≤ 3) 둘째 줄에는
www.acmicpc.net
문제
원래 단어와 목표 단어가 주어졌을 때, 단어의 글자를 치환해 다른 단어로 바꿀 수 있는지를 묻는 문제입니다.
예를 들어 ppap를 |>|>0|>로 바꾸려면 p를 |>로, a를 0으로 치환할 수 있습니다.
만약 baa를 |>0>로 바꾼 다면, a에 매칭되는 문자를 찾을 수 없어 불가능합니다.
아이디어
문자열의 길이는 최대 15, 한 알파벳과 대응되는 문자열은 최대 3 길이를 가지니, 모든 경우를 구해 해결할 수 있습니다.
1. 두 문자열의 0번 인덱스에서 시작합니다.
2. 만약 현재 문자에 대응하는 리트가 없다면, 대응되는 문자열에서 1~k개를 리트로 정하고 다음 문자로 넘어갑니다.
3. 만약 현재 문자에 대응하는 리트가 있다면, 두 문장을 확인해 리트가 들어맞는지 확인하고, 다음 문자로 넘어갑니다.
4. 두 문자열의 끝에 동시에 도달하면 가능한 경우입니다. 그렇지 않으면 불가능합니다.
코드
#include <iostream>
#include <string>
#include <algorithm>
#include <array>
using namespace std;
int k;
string s1, s2;
array<string, 26> leet;
bool solve(size_t idx1, size_t idx2) {
if (idx1 == s1.size() && idx2 == s2.size())
return true;
else if (idx1 == s1.size() || idx2 == s2.size())
return false;
if (leet[size_t(s1[idx1])].empty()) {
for (int i = 1; i <= k && idx2 + i <= s2.size(); i++) {
leet[size_t(s1[idx1])] = s2.substr(idx2, i);
if (solve(idx1 + 1, idx2 + i))
return true;
}
leet[s1[idx1]] = "";
return false;
}
else {
auto lt = leet[size_t(s1[idx1])];
if (lt == s2.substr(idx2, min(lt.size(), s2.size() - idx2)))
return solve(idx1 + 1, idx2 + lt.size());
else
return false;
}
}
int main(void) {
int T; cin >> T;
for (int i = 0; i < T; i++) {
cin >> k >> s1 >> s2;
for_each(s1.begin(), s1.end(), [] (char &ch) { ch -= 'a'; });
leet = array<string, 26>();
if (solve(0, 0))
cout << 1 << '\n';
else
cout << 0 << '\n';
}
}