이번 문제는 백준의 골드 4 문제 단어 섞기 문제이다.
문제를 차근차근 한 번 읽어보자.
두 단어를 섞어 주어진 단어를 만들 수 있는지 판단해야 한다.
단, 원래 단어의 순서는 유지되어야 한다.
최대 1000개의 데이터가 주어지며, 단어는 400글자가 최대이다.
주어지는 데이터의 수가 그렇게 크지 않으니 다양하게 생각해보자.
문제를 어떻게 풀어나가야 할까?
포인터의 활용
처음 든 생각은 포인터를 총 3개 만들어 탐색하는 것이다.
주어지는 2개의 단어를 짚을 포인터 2개 그리고, 타겟용 하나.
3개의 포인터를 앞으로 옮겨가며 탐색하는 것은 어떨까?
타겟의 포인터를 기준으로 해당 알파벳이 주어진 단어에 있으면,
해당 단어의 포인터만 앞으로 한 칸 옮기는 것이다.
그럼 순서는 반드시 지켜질 것이고, 어차피 중복되는 알파벳이
나오더라도 반드시 두 번 타겟에 등장해야 하기 때문에,
괜찮은 로직이라고 생각된다. 한 번 구현해보자.
int src1_ptr = 0, src2_ptr = 0;
for (int target_ptr = 0; target_ptr < target.size(); target_ptr++) {
if (target[target_ptr] == src1[src1_ptr])
src1_ptr++;
else if (target[target_ptr] == src2[src2_ptr])
src2_ptr++;
}
if(src1_ptr == src1.size() && src2_ptr == src2.size())
cout << "Data set " << (i + 1) << ": yes";
else
cout << "Data set " << (i + 1) << ": no";위와 같이 로직을 구현해보았는데, 문제가 생겼다.
만약 cat tree catrtee가 주어졌다고 생각해보자.
내 로직대로라면, cat을 먼저 찾아버리면 rtee가 남아
만들 수 없는 단어가 되어버린다, 하지만 실제론 그렇지 않다.
ca를 찾은 뒤 tr을 찾으면, 가능한 타겟임을 알 수 있다.
그래서 둘 다 가능한 알파벳일 때 분기를 하나 더 추가했다.
포인터의 진행도가 더 낮은 단어의 포인터를 늘려주는 것이다.
하지만 안타깝게도 이 로직은 실패했다.
사실 반례를 찾지 못해서 어떤 부분이 틀린 것인지 아직 모르겠다.
DP
조금 더 생각하다 다른 사람의 풀이를 참고했다.
사실 이 문제는 DP 문제라고 한다.
Memoization을 위해 2차원 배열을 만들어 저장한다.
이 때 행은 첫 번째 단어를, 열은 두 번째 단어를 의미함을 가정한다.
예컨대, cat이 행이고 tree가 열이 되는 것이다.
1열과 1행 채우기
가장 먼저 1열과 1행, 즉 기본적으로 단어들을 어디까지 만들 수 있는지 검사한다.
예를 들어, 1열을 통해 cat과 tcraete를 검사한다고 해보자.
둘은 순서상 동일한 알파벳이 없으므로, 모두 0이다.
1행을 통해 tree와 tcraete를 검사한다면?
둘은 제일 앞의 알파벳 t만 동일하기 때문에 1 0 0이 될 것이다.
이 때 중요한 점은, 첫 글자가 같을 때부터 1으로 만들기 위해 dp[0][0]
즉, 가장 첫 번째 칸은 기저 조건으로 항상 1로 초기화 해야 한다.
내부 채우기
이제 내부를 채워나가면서, 만들 수 있는 단어인지 검사한다.
열을 보았을 때, 이전 글자가 만들 수 있는 글자고 현재 알파벳이 같다면?
if (dp[i - 1][j] && (src1[i - 1] == target[i + j - 1]))
dp[i][j] = 1;dp[i][j] 즉, 첫 번째 단어의 i번째와 두 번째 단어의 j번째 까지의
알파벳을 조합해서 타겟을 i + j 번째 까지 만들 수 있다는 의미이다.
행을 보았을 때, 이전 글자가 만들 수 있는 글자고 현재 알파벳이 같다면?
if (dp[i][j-1] && (src2[j - 1] == target[i + j - 1]))
dp[i][j] = 1;위에서 열을 보았을 때의 조건과 동일하다.
따라서, 타겟의 i + j 번째 까지 만들 수 있다는 의미이다.
두 조건을 합쳐서 하나의 조건으로 만들면 아래의 코드와 같다.
for (int i = 1; i <= src1.size(); i++) {
for (int j = 1; j <= src2.size(); j++) {
if ((dp[i - 1][j] && (src1[i - 1] == target[i + j - 1])) || (dp[i][j - 1] && (src2[j - 1] == target[i + j - 1])))
dp[i][j] = 1;
}
}결국 우리는 dp[첫 번째 단어 길이][두 번째 단어 길이]의 값이 1이면
타겟을 만들 수 있는 경우임을 알 수 있다.
그 이외에는 모두 만들 수 없는 경우로 간주해도 무방하다.
결론
이게 DP 문제일 줄은 꿈에도 몰랐다.
하지만 생각해보면, 내가 접근한 포인터 개념과 크게 다르지 않다고 생각한다.
첫 번째 단어의 i와 두 번째 단어의 j를 검사할 때, 타겟의 i + j를 검사하는게
내가 앞서 생각했던 3개의 포인터 방식과 유사한 것 같다.
다만 다른 점이 있다면, 중복되는 알파벳이 있을 때 둘 다 1로 표시하여
어차피 dp[i][j] 값이 1이 됨을 이용해 통과를 시킨다는 점인데,
나도 이 부분은 분기를 통해서 해결을 했다고 생각한다.
어떤 점이 달라서 내 풀이는 틀리게 되는지 좀 더 생각해보아야 할 것 같다.
결론 (12.10 15:54 수정)
내 로직의 문제점을 발견했다.
예를 들어, cat tree cattreet의 경우 내 코드는 동작하지 않는다.
그 이유는 cat과 tree는 모두 나오기 때문에,
포인터는 옳은 방향대로 단어들의 사이즈까지 증가하기 때문이다.
즉, 틀린 경우이지만 틀렸다고 잡을 수 없게 된다.