프로그래머스 - 단어변환

단어변환 (2021. 06. 20) BFS/DFS

Programmers
Git Solution

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

질의 케이스

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0
"hit"	"hhh"	["hhh","hht"]	2

그래프 표현

           hit
            |
           hot
          /    \
        dot    lot
        |   \     \
        dog  lot  log
        |   \    \
        cog  log  log

단어별 포함 워드리스트

hit[hot]
hot[dot, lot]
dot[hot, dog, lot]
dog[dot, log, cog]
lot[hot, dot, log]
log[dog, lot, cog]
cog[dog, log]

수행 결과

테스트 번호	통과여부	메모리 및 시간
테스트 1	통과	(5.77ms, 53MB)
테스트 2	통과	(7.49ms, 53.2MB)
테스트 3	통과	(31.36ms, 53.2MB)
테스트 4	통과	(4.45ms, 54.2MB)
테스트 5	통과	(3.61ms, 52.3MB)

문제 해결

해당문제를 해결하는데 가장 중요한 포인트는 2가지 였던것 같다.

• 다음 노드의 집합을 찾을 수 있는가
• 찾은 노드의 집합군을 어떻게 처리할 것인가
  • target의 정확한 위치값은 필요하지 않다. 해당 집합군에 포함되어 있는가 이다.
  • 집합군이 없을 경우, 카운트의 횟수와 집합군을 롤백해야 한다.

오랜시간이 걸려서 원하는 결과를 얻었지만, 실제 테스트 3 케이스에서 계속 실패를 하였는데, 찾아보니 다음과 같은 상황이 발생했다.

hit -> ["hht"] 인경우

람다로 두 리스트를 contains하여 개수를 반환하였는데 위의 경우는 값이 2가 나와야 하는데 실제로는 3의 값이 나온다. 그 이유는

• [h]ht 인경우 hit.contains true
• h[h]t 인경우 hit.contains true
• hh[t] 인경우 hit.contains true

코드를 변경하였고 이후 실제 테스트3의 케이스도 통과하였다.

코드 1) - matchSize에 해당하는 리스트 만드는 코드

List<String> containList = wordList.stream().map(s -> {
    if(matchSize == getMatchSize(Arrays.asList(s.split("")), beginList)){
        if(!visitList.contains(s)){
       		return s;
        }
    }
    return null;
}).filter(Objects::nonNull).collect(Collectors.toList());

코드2) - matchSize 구하는 코드

return IntStream.range(0, Math.min(list1.size(), list2.size()))
                .filter(idx -> list1.get(idx).equals(list2.get(idx))).count();