프로그래머스 [Lv. 4] 단어 퍼즐 {언어 : Python}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12983?language=python3

프로그래머스

정답 코드

from collections import deque
def solution(strs, t):
    n = len(t)
    answer = -1
    lengthDict = dict()
    for s in strs:
        length = len(s)
        if not lengthDict.get(length, 0):
            lengthDict[length] = dict()
        lengthDict[length][s] = 1
    listT = list(t)
    visited = [0] * (n+1)
    dq = deque([])
    for i in range(min(n, 5), 0, -1):
        string = "".join(listT[:i])
        if lengthDict.get(i, 0) and lengthDict[i].get(string, 0):
            dq.append(i)
            visited[i] = 1
    
    while dq:
        length = dq.popleft()
            
        for i in range(min(length+5, n), length, -1):
            string = "".join(listT[length:i])
            newLen = i - length
            if lengthDict.get(newLen, 0) and lengthDict[newLen].get(string, 0) and visited[i] == 0:
                visited[i] = visited[length] + 1
                dq.append(i)
    if visited[n]:
        answer = visited[n]
    return answer

풀이 방법

1. 길이를 key로 dict()를 value로 하는 딕셔너리를 만든다.
2. 이 딕셔너리에 길이에 맞게 strs의 요소들을 저장한다.
3. t를 list로 분해한다.
4. 인덱싱을 이용해서 1~5만큼의 길이로 제단하고 딕셔너리에 있는지 확인한다.
5. visited를 이용해서 현재 지점에 값이 있을 경우 이미 도달한 최소 count가 있는 것이므로 중복해서 탐색하는 일을 없게 만든다.
6. 이후 visited의 n번째 인덱스에 값이 있으면 strs의 요소들로 t를 만들 수 있는 것이므로 visited[n]값을 answer로 치환하면 끝!

느낀점

• 시간초과가 나는 이유를 이미 탐색한 부분을 중복해서 탐색하기 때문이라고 판단했다.
  • 예를들어 abcdabcdabcd가 t이고 strs의 요소가 [abcd, a, b, c, d]라고 한다면
  • abcd만큼 탐색 했을 때가 최소 이고
  • a + b + c + d만큼 탐색했을 때는 이미 abcd가 visited[4]부분에 값을 저장했고 이 값이 최소이므로 탐색을 하지 못하게 만든다는 말이다.
• 해가 거듭될 수록 같은 레벨이라도 오래된 문제는 비교적 쉬운 것 같다.
• 다음에 javascript로 리팩토링을 하면 좋을 것 같다.