[프로그래머스] <단어 변환> 파이썬

programmers.co.kr/learn/courses/30/lessons/43163

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

BFS 이용

 

from collections import deque

def solution(begin, target, words):
    if target not in words : return 0
    
    answer = 0
    check = [0] * (len(words)+1)
    visited = [False] * (len(words)+1)
    words.append(begin)
    
    def function(index) :
        queue = deque()
        queue.append(index)
        visited[index] = True
        while queue :
            v = queue.popleft()
            if words[v] == target : return check[v]
            count = [0] * len(words)
            for i in range(len(words)) :
                for j in words[v] :
                    if j not in words[i] : count[i] += 1
            for i in range(len(count)) :
                if count[i] == 1 and not visited[i] :
                    visited[i] = True
                    check[i] = check[v]+1
                    queue.append(i)
    a = function(len(words)-1) 
    if a : return a
    else : return 0

 

구글링 없이 푼다고 아득바득두시간 머리싸메고 풀었는ㄷ

 

정확성 테스트

테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.22ms, 10.3MB)
테스트 3 〉	실패 (0.65ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (0.00ms, 10.3MB)

채점 결과

정확성: 80.0

합계: 80.0 / 100.0

 

 

문제는 같은자리인지는 확인안하고 다른 갯수만 찾았다는 거임

풀었다 나이스 구글링했지만 아무튼

from collections import deque

def solution(begin, target, words):
    if target not in words : return 0
    
    answer = 0
    check = [0] * (len(words)+1)
    visited = [False] * (len(words)+1)
    words.append(begin)
    
    def function(index) :
        queue = deque()
        queue.append(index)
        visited[index] = True
        while queue :
            v = queue.popleft()
            if words[v] == target : return check[v]
            count = [0] * len(words)
            for i in range(len(words)) :
                count[i] = [True for x, y in zip(words[v],words[i]) if x != y]
            for i in range(len(count)) :
                if len(count[i]) == 1 and not visited[i] :
                    visited[i] = True
                    check[i] = check[v]+1
                    queue.append(i)
    a = function(len(words)-1) 
    if a : return a
    else : return 0

정확성 테스트

테스트 1 〉	통과 (0.02ms, 10.4MB)
테스트 2 〉	통과 (0.13ms, 10.3MB)
테스트 3 〉	통과 (0.76ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10.3MB)
테스트 5 〉	통과 (0.00ms, 10.3MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0