링크: https://programmers.co.kr/learn/courses/30/lessons/43163
문제:
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
[규칙]
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
코드:
def diff(str1, str2):
res = 0
for i in range(len(str1)):
if str1[i] != str2[i]:
res += 1
return res
def solution(begin, target, words):
cnt= 0
if target not in words:
return 0
while begin != target:
replace = [word for word in words if diff(begin, word) == 1]
if not replace and begin != target:
return 0
if len(replace)>1:
replace.sort(key=lambda x: diff(begin, x))
begin = replace[-1]
words.remove(begin)
cnt += 1
return cnt
쉽게 생각하면 쉽게 풀리는 문제다.
1. 우선 규칙 1번에 따라 words에 있는 단어 중 한 개의 알파벳만 다른 단어를 찾는다. -> replace: List[str]
2. 아직 begin과 target이 같지 않은데 바꿀 수 있는 단어가 없다면 변환할 수 없는 경우다.
3. 바꿀 수 있는 단어가 1개 이상이라면, 정답과 가장 가까운(개수 차이가 가장 적은) 단어를 찾는다. -> replace를 거리가 먼 순으로 정렬
4. begin은 바꿀 수 있는 단어 중 정답과 가장 가까운 단어 -> replace[-1]
5. 한번 바꾼 건 다시 사용하지 않으니까 words에서 제거 -> words.remove(begin)
6. 단계 하나 증가 -> cnt += 1
문제에서 '최소 몇 단계의 과정을 거쳐'라고 해서 BFS로 구현해야 할 거같아서 고민하다가, 우선 떠오르는 쉬운 풀이를 해보고 안되면 구현하려고 했는데 다행히 한번에 통과했다.
'Algorithm > Python' 카테고리의 다른 글
[파이썬/LeetCode 792]Number of Matching Subsequences (0) | 2021.06.23 |
---|---|
[파이썬/프로그래머스]여행경로 (0) | 2021.05.18 |
[파이썬/프로그래머스]방금그곡 (0) | 2021.05.12 |
[파이썬/백준 1270]전쟁 - 땅따먹기 (0) | 2021.05.11 |
[파이썬/프로그래머스]순위검색 (0) | 2021.05.10 |