[LeetCode] 433. Minimum Genetic Mutation

출처 : https://leetcode.com/problems/minimum-genetic-mutation/

Minimum Genetic Mutation - LeetCode

 

 

 

1. 문제 설명 

유전자 문자열은 A, C, G, T로 이루어진 길이 8의 문자열이다. start문자열은 유전자 문자열이고, end문자열은 돌연변이 문자열이다. (돌연변이 문자열이 아닐 수도 있다) start배열에서 단일 문자를 변경하여 돌연변이 문자열(end)이 될 수 있는 유효한 문자열은 bank배열에 저장되어 있다. 다시 말해서, bank배열에 저장되어 있는 문자로만 변경하면서 end배열이 되어야 한다.

start문자열에서 단일 문자를 최소 개수만큼 사용하여 end문자열로 바꿨을 때의 가장 적은 방법의 수를 반환하라. 

 

 

 

 

2. 접근 방식

queue에 start문자열과 0(=최소 방법의 수)을 넣는다. start문자열의 각 문자를 ATGC를 한번씩 사용해서 변경한 후 bank배열에 존재하는 지 확인한다. 존재한다면, bank배열에 존재하는 문자열을 제거 후 카운트를 누적시키고 다시 queue에 바뀐 문자열을 넣고 while반복문을 돌면서 start문자열과 end가 같은 문자열일 때 까지 돈다. 

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        # [1] initialize queue with starting gene
        q, bank = collections.deque([(start,0)]), set(bank)

        while q:
            g, m = q.popleft()
            if g == end : return m
            
            # [2] try all possible mutations, namely,
            #     try every nucleotide in each position
            for i in range(len(g)):
                for n in "ATGC":
                    gm = g[0:i] + n + g[i+1:]
                    # [3] successful branches are added to
                    #     the queue for further mutagenesis
                    if gm in bank:
                        bank.remove(gm)
                        q.append((gm, m+1))
        
        return -1

 

 

4. 분석

1. Time : 문자열이 만들어질 때 마다 모든 경우의 수를 체크하니까 O(N^2)이 아닐까 싶다. 
2. Space :
3. 소요시간 : 1시간 30분 이상 
4. 제출 횟수 (무작정 제출하기 않기)  : 5회 이상 
5. 어려웠던 부분과 해결한 방법

- 이 방법은 bfs를 활용한 방법이다. 조금만 더 머리를 썼다라면, 떠올랐을 수도 있는데 문자열을 bfs를 사용하여 문제를 푼 경험이 없어서 떠오르지가 않았다. 

6. 실수가 줄어들었는가 ?