[Algorithm] 단어변환

코딩테스트 연습 - 단어 변환

아니 풀긴 했는데 ㅋ 다른 사람 풀이 분석 해야 할듯? 2시간 정도 걸림

소요 시간

약 2시간

 

해결 과정

begin =  "hit"

"hit" -> "hot" -> "dot"  ...

 

문제에 있는대로 그대로 따라갔다. 일단, 가장 짧은 변환 과정을 찾아야 하는데 모든 과정 중에서 가장 짧은 과정을 찾아야 했다. 그래서 무조건 다 탐색해두고, 그 중에 개수가 가장 작은 것을 찾아야 겠구나. (전체 구조 확인)

 

2번째 예시로 target이 words에 없는 경우, 0을 반환하는 경우를 보여줬다. 이 부분을 코드 첫 부분에 써서 이후 과정을 실행하지 않아도 되면 무조건 return 하기로 했다.

if target not in words:
	return 0

 

우선, begin과 한 글자만 다른 것을 words에서 찾아줘야 한다. 이 일련의 과정은 계속 쓰일 것이기 때문에 함수로(findNextWordList) 따로 빼서 만들기로 했다. 이 함수에서는 한 글자만 다른 word를 뽑아야 했는데, numpy를 쓰려다가 에러가 나서 (그리고 코테에서 numpy 안쓰는 것 같길래) 나중엔 그냥 for문 돌려서 한 글자씩 비교해서 확인해줬다.

이 함수에는 매개변수로 word(탐색대상), words 를 줘야하는데, 이미 단계 속에 포함된 word는 제외하고 넣어주기 위해 remainList를 다음과 같이 뽑아줬다. 

remainedList = list(set(words) - set(currentList))

 

처음에는 [begin, i]를 먼저 넣어주고 시작했는데, 리팩토링 후에는 queue에 [begin]만 넣어두고 while 문 내부 코드와 합쳤다. 

 

queue = [[], [], ...]

 

queue를 활용해 탐색했다. queue.popLeft()로 하나 씩 빼주면서 변환리스트가 완성되지 않았을 때는 queue.append()를 해줬다.

 

[변환리스트가 완성되려면?] 맨 뒷 원소가 target이거나, findNextWordList의 결과가 없을 때 , 새로운 리스트 (finalArray)에 담아줬다. queue의 원소를 모두 탐색했다면, 이제 finalArray에서 맨 뒤의 원소가 target인 대상만 골라주고, 거기서 원소 개수가 가장 적은 것을 return 해주면 된다.

 

나의 풀이

from collections import deque

def findNextWordList(begin, words):
    wordList = []
    for element in words:
        # 문자열 1개만 다른지 확인
        num = 0
        for i in range(len(element)):  # zip을 이용할 수도 있음
            if element[i] != begin[i]:
                num += 1
        if num == 1:
            wordList.append(element)
    return wordList

def solution(begin, target, words):
    queue = deque()

    # target 없는 경우
    if target not in words:
        return 0

    # 이 한 줄로 여러 줄 없애고 while문을 타게 했음.
    queue.append([begin])

    finalArray = []
    while queue:
        currentList = queue.popleft()
        #words에서 currentList에 있는 것 제거
        remainedList = list(set(words) - set(currentList))
        wordList = findNextWordList(currentList[-1], remainedList)
        if len(wordList) == 0 or currentList[-1] == target:
            finalArray.append(currentList)
            continue
        for i in wordList:
            queue.append(currentList + [i])

    resultArray = []

    for element in finalArray:
        if element[-1] == target:
            resultArray.append(len(element) - 1)

    if resultArray:
        return min(resultArray)
    else:
        return 0

 

첫 번째 시도 코드

from collections import deque

queue = deque()

def findNextWordList(begin, words):
    wordList = []
    for element in words:
        # 문자열 1개만 다른지 확인
        num = 0
        for i in range(len(element)):
            if element[i] != begin[i]:
                num += 1
        if num == 1:
            wordList.append(element)
    return wordList
    
def solution(begin, target, words):
    
    # target 없는 경우
    if target not in words:
        return 0
    
    wordList = []
    wordList = findNextWordList(begin, words)
    
    # 바로 다음 word 없는 경우
    if len(wordList) == 0:
        return 0
    
    for i in wordList:
        queue.append([begin, i])
        
    
    tempArray = []
    while queue:
        tempList = queue.popleft()
        # words에서 tempList에 있는 것 제거
        if tempList:
          myList = list(set(words) - set(tempList))
          wordList = findNextWordList(tempList[-1], myList)
          if len(wordList) == 0 or tempList[-1] == target:
              tempArray.append(tempList)
              continue # 아 어떻게 빠져나가지?
          for i in wordList:
              queue.append(tempList + [i])
    
    resultArray = []

    for element in tempArray:
        if element[-1] == target:
            resultArray.append(len(element))
    
    if resultArray:
      return min(resultArray) - 1
    else:
      return 0

 

 

다른 풀이

우선 제일 상단에 있는 풀이들을 보면 보든 경우의 수를 따진게 아닌 듯 한데.. 신기하네

 

findNextWordList를 다음과 같이 한 줄로 가능 ㅋ 

if sum([x!=y for x, y in zip(word_1, word_2)]) == 1: