단어 퍼즐

• n = 문자열 t의 길이, m = 배열 strs의 크기, k = 단어 조각의 길이
• dp[i] 를 t[:i+1]을 만들기 위해 사용하는 최소의 단어 수라고 하면, 간단히 점화식이 세워진다.
  • dp[i] = min_k(dp[i-k] + 1), where t[i-k:i+1]∈strs
• 문제 조건에서는 1≤k≤5 이므로 dp테이블을 크기가 t인 리스트로 만드는 대신에, 크기가 5인 리스트만 유지하면서 슬라이딩 윈도우 방식으로 계산하는 것도 가능하다. 그러나 실제로 그렇게 구현은 하지 않았다.
• 저 점화식을 계산하려면 i에 대한 루프를 한번 돌 때마다, k개의 문자열에 대해서 문자열이 strs 안에 포함되는지를 체크해야 한다. 포함여부를 O(1)에 체크하기 위해서, 미리 O(m)시간에 strs를 set으로 변환하는 전처리가 필요하다.
• 이렇게 전처리를 한다면, k≤5를 그냥 상수 취급할 때, 시간 복잡도는 O(m+n)이다
• 만약, k를 상수취급하지 않고, 복잡도 계산에 포함시킨다면, set을 만드는 데에는 O(mk)이 들고, k길이의 문자열 k개를 set에서 포함여부를 확인하는 것은 O(k^2), 그래서 총 O(mk + nk^2)이 걸린다. 이것을 효율적으로 하기 위해서는, Rabin fingerprint와 같은 rolling hash를 이용해서, k길이 문자열에 대한 해시를 O(1)에 계산해줄 수 있다. 그러면 문자열 한개의 set비교 코스트가 O(k)에서 O(1)로 줄게 되므로, k개의 문자열에 대한 비교를 총 n번 하는 시간은 O(nk). 그래서 총 시간을 O(mk + nk)로 단축시킬 수 있다.
  • 물론 이 문제에서는 k가 5밖에 안되므로, 이렇게 구현한 코드 2가 그냥 구현한 코드 1 보다 더 느렸다..

"""Solution code for "Programmers 12983. 단어 퍼즐".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12983
- Solution link: http://www.teferi.net/ps/problems/programmers/12983
"""

INF = float('inf')


def solution(strs, t):
    strs_set = set(strs)
    dp = [0] * (len(t) + 1)
    for i in range(1, len(t) + 1):
        dp[i] = min((dp[prev] + 1
                     for prev in range(max(0, i - 5), i)
                     if t[prev:i] in strs_set),
                    default=INF)
    return dp[-1] if dp[-1] != INF else -1

"""Solution code for "Programmers 12983. 단어 퍼즐".

Using Rabin-fingerprint for string matching.
- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12983
- Solution link: http://www.teferi.net/ps/problems/programmers/12983
"""

from teflib import string

INF = float('inf')


def solution(strs, t):
    p_hashes = set(string.fingerprint(s) for s in strs)
    t_hashes = [list(string.gen_fingerprints(t, l)) for l in range(1, 6)]
    dp = [0] * (len(t) + 1)
    for i in range(1, len(t) + 1):
        dp[i] = min((dp[i - x] + 1
                     for x in range(1, min(5, i) + 1)
                     if t_hashes[x - 1][i - x] in p_hashes),
                    default=INF)
    return dp[-1] if dp[-1] != INF else -1

• Dependency: teflib.string.fingerprint, teflib.string.gen_fingerprint