코딩 인터뷰 완전 분석 215쪽 문제 18.10 풀이 Etc

문제

『코딩 인터뷰 완전 분석』215쪽 고난이도 연습문제 18.10

사전에 등장하고 길이가 같은 두 단어가 주어졌을 때, 한 번에 글자 하나만 바꾸어 한 단어를 다른 단어로 변환하는 프로그램을 작성하라. 변환 과정에서 만들어지는 각 단어도 사전에 있는 단어여야 한다.

[실행 예]

input : DAMP, LIKE
output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

[사전 데이터]

네 글자 단어 - word4

다섯 글자 단어 - word5

 

[심화 문제 - 풀지 않아도 됩니다]

심화문제 1: 가장 적은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다.
심화문제 2: 가장 많은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다. 단, 변환 과정에서 같은 단어가 두 번 나오면 안됩니다.

 

풀이

이건 심화문제가 좀 어려울 것 같은데.. 일단 간단히는 네 글자나 다섯 글자이므로 최대 4*3*2*(사전 크기) 만큼 재귀적으로 검색해서 방법을 찾을 수 있겠다.

그런데 이 방법은 너무 느리다. 특히나 사전 크기가 조금만 커져도 이건 못 써먹는다. 여기서 lexicographical한 순서를 따져 pruning을 할 수도 있을 것 같은데, 그다지 효과적일지 모르겠다.

그리고 이 방법의 최대 문제점은.. 돌아서 찾을 수가 없다는 것이다. 예컨데, 단어의 글자들을 한번씩 변형해서 찾게만 해놓았기 때문에 cadgy, janty와 같은 경우,

cadgy -> caddy -> candy -> canty -> janty

로 갈 수 있음에도 불구하고 IMPOSSIBLE을 출력하게 된다. (한 글자들을 한번씩 바꾸는 것으로 문제를 착각해버린 탓에..orz)




결과

input: damp, like
output: damp -> lamp -> limp -> lime -> like

input: rice, rach
output: rice -> race -> rach

input: grit, brow
output: grit -> grot -> grow -> brow

input: cadgy, janty
output: IMPOSSIBLE

소스코드

우선 'wordMatching' 이라는 함수로 시작 단어와 끝 단어가 존재하는지 검사하고, 재귀함수를 시작하게 하거나 끝나고 나서의 자잘한 처리를 하게끔 했다.

'startMatching' 에서 실제로 재귀적인 검색에 들어가는데, 입력단어가 찾으려는 단어와 같은지 종료검사를 한 뒤, 최종 단어와 다른 각 요소들에 대해서 하나씩 분기하여 체크하는 방식으로 들어간다. 이 경우, 인덱스 순서대로 검사하여 먼저 찾으면 종료한다. 단어 길이보다 적은 단계수를 확신하지만, 단어 길이보다 긴 단계로 찾지 못한다.


int        startMatching(string strFrom, const string &strTo, const vector< string > &db, vector< string > &output)
{
if( strEqual(strFrom, strTo) ) return 1;

for(int i = 0; i < strFrom.size(); ++i)
{
if(strFrom[i] == strTo[i]) continue;

string strTrans = strFrom;
strTrans[i] = strTo[i];

if( isWordExists(strTrans, db) )
{
output.push_back( strTrans );
if( startMatching(strTrans, strTo, db, output) == 1 ) return 1;
output.pop_back();
}
}

return -1;
}

int wordMatching(const string &strFrom, const string &strTo, const vector< string > &db)
{
// check availability
bool isFromHere = false;
bool isToHere = false;
for(int i = 0; i < db.size(); ++i)
{
if(strEqual(strFrom.c_str(), db[i].c_str())) isFromHere = true;
if(strEqual(strTo.c_str(), db[i].c_str())) isToHere = true;
}

if(!isFromHere || !isToHere) return -1;

vector< string > output;
output.push_back(strFrom);
if( startMatching(strFrom, strTo, db, output) == 1 )
{
for(int i = 0; i < output.size()-1; ++i)
{
printf("%s -> ", output[i].c_str());
}
printf("%s\n", output[ output.size()-1 ].c_str());

return 1;
}

return -1;
}

덧글

댓글 입력 영역