Programmers. 단어 퍼즐

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 단어 퍼즐

문제 풀이

dp와 완전 탐새을 섞은 문제다. 레벨 4로 마킹되어 있지만 카카오 코테에 출제되었다면 레벨 3에 3번 정도에 위치하지 않았을까 싶다. 첫 글자부터 마지막 글자까지 순회하며 단어 조각의 길이가 1에서 5까지만 존재함을 유념해 하위 문제와 결합을 어떻게 할 지 고민해야 한다.

특히 하위 문제의 값을 기록한 좌표와 가능한 퍼즐 조각의 길이만큼의 좌표를 잘 추출해야 문제를 수월히 해결할 수 있다.

• 1부터 t의 길이만큼의 dp 배열 생성
• 초항(첫 번째 글자) 체크 후 dp[0]에 입력
• 가능한 퍼즐 조각 길이 1부터 5에 대해 해당 퍼즐 조각 이전 dp 좌표가 valid한 지 체크하고 퍼즐 조각만큼 길이에 대해 배열에 존재하는 지 탐색, 존재하면 현재 dp좌표를 갱신한다.
• 순회를 모두 마치고 마지막 자리에 대해 valid하면 값을 반환하고 그렇지 않으면 -1을 반환한다.

python 코드

def solution(strs, t):
    if t in strs:
        return 1
    INF = float('inf')
    dp = [INF] * len(t)
    if t[0] in strs:
        dp[0] = 1
    for i in range(1, len(t)):
        if t[:i + 1] in strs:
            dp[i] = 1
        for j in range(1, 6):
            if i >= j:
                if dp[i - j] != INF and t[i - j + 1:i+1] in strs:
                    dp[i] = min(dp[i], dp[i - j] + 1)
    answer = -1
    if dp[-1] != INF:
        answer = dp[-1]
    return answer