[프로그래머스] LV.2 단어 변환 / 파이썬(Python)

 

📜 문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

 

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

💡 문제 풀이

또또 굉장히 오랜만에 올리는 문제 풀이( ˃ ⩌˂)

나는 개발자로 일하다가 지금은 1년 6개월째 IT프로젝트를 관리하는 PM으로 업무를 하고 있다. PM을 하기에는 프로젝트 경험도, 지식도, 짬도 한참한참 부족하지만 어쩌다보니 정신차리고 보니 pm이 되어있었다.. 업무도 직무도 모든 것이 너무너무 익숙하지 않아서 처음에는 엄청 헤매고 땔치고 다시 개발이나 해야하나 엄청 고민을 많이 했었는데 어느덧 많이 익숙해지긴 했다.. (익숙해졌다고 했지 매니징 실력이 늘었다고는 하지 않았다... 조금이라도 늘었나..?) 피엠 직무를 하다보니 직접적으로 개발에 관여할 일은 상당히 한정적이었고 피엠 직무에 익숙해지기 위해서 에너지를 많이 썼다. 그러다보니 현직 개발자일때 보다 개발 근손실이 엄청났던 것 같다... 근데 나는 개발하는걸 너무너무 좋아한다. 즐긴다. (라고 말하기에는 좀 손을 놨었지만)

이상 그동안 깃 커밋도 열심히 안하고 1일 1솔도 안하고 블로그 글도 안쓴거에 대한 구구절절한 변명이었다 흙흙.. 아무도 이 글을 자세히 안읽겠지만 내 자신에게 하는 셀프 변명이랄까... 그리고 아래 코드라인이 엉망인거에 대한 변명이기도 하다. 

 

단어를 한 글자씩 바꿔서 목표 단어에 접근해야 하는 문제. bfs로 접근하면 되겠다 생각은 했는데 풀다보니 겁나 야메같고 근본없는 코드가 완성되었다. 룰루~~~ 테스트코드 몇개나 떨어질려나? 하고 돌렸더니 다 통과????? 이거 정말 럭키비키쟈나???? 아니고 제대로 다시 풀어봐야겠다. 내가 문제를 푼 방식은 딱히 어떤 알고리즘이라고 하기 어렵고... 정말 단순구현인데 효율성도 엉망일텐데 레벨2 문제를 통과해서 좀 놀랬다. bfs가 있었는데요... 없었습니다?????

내가 문제에 접근한 방식

1. 기존 단어에서 target단어를 만들 수 없는 경우 종료 

2. 현재 단어와 target 단어를 비교해서 한 글자만 다르면 목표에 도달했기 때문에 종료

3. 위의 두 경우가 아닌 상황에 주어진 단어랑 순서대로 비교해서 한 글자만 다른지 비교하고

    1. 한 글자만 다르면 비교한 단어로 갱신

    2.그렇지 않을 경우 그 다음 단어랑 비교해봄

 

목표에 도달할 때 까지 위의 순서 반복

분명히 얄궂은 테스트케이스 넣으면 떨어질것 같다... bfs로 다시 풀어봐야겠다 (제발... 다시 안풀면 누가 게으른 저를 좀 혼내주세요)

def solution(begin, target, words):
    answer = 0
    
    if target not in words:
        return answer
    
    idx = 0ㅁ
    while begin != target:
        if check(begin, target):
            answer += 1
            return answer
        
        if check(begin, words[idx]):
            begin = words[idx]
            answer += 1
            idx += 1
        else:
            if idx <= len(words):
                idx += 1
            else:
                idx = 0

    return answer

def check(word1, word2):
    diff = 0
    if len(word1) != len(word2):
        return False
    else:
        for i in range(len(word1)):
            if word1[i] != word2[i]:
                diff += 1
    
    if diff == 1:
        return True
    return False