문제 개요
모든 문자열의 길이가 동일한 문자열 리스트 words와 하나의 문자열 target이 주어졌다고 가정해 보겠습니다. 아래 규칙에 따라 주어진 단어들을 사용해 target을 생성해야 합니다.
- target은 반드시 왼쪽에서 오른쪽 순서로 생성합니다.
- target의 i번째 문자(0부터 시작하는 인덱스)를 만들려면, target[i]가 words[j][k]와 일치할 때 words의 j번째 문자열에서 k번째 문자를 선택하면 됩니다.
- 일단 어떤 문자열의 k번째 문자를 사용했다면, 이후에는 모든 문자열에서 k번째 위치와 같거나 앞에 있는 문자(x ≤ k)는 더 이상 사용할 수 없습니다.
- 이 과정을 반복하여 target 문자열 전체를 완성합니다.
즉, words로 target을 만들 수 있는 서로 다른 방법의 총 개수를 구해야 합니다. 답은 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환합니다.
예시
입력이 words = ["pqqp", "qppq"], target = "qpq"라고 하면 출력은 4가 됩니다. 가능한 조합은 다음과 같습니다.
- "qpq" → qppq의 인덱스 0, qppq의 인덱스 1, pqqp의 인덱스 2
- "qpq" → qppq의 인덱스 0, qppq의 인덱스 1, qppq의 인덱스 3
- "qpq" → qppq의 인덱스 0, qppq의 인덱스 2, qppq의 인덱스 3
- "qpq" → pqqp의 인덱스 1, qppq의 인덱스 2, qppq의 인덱스 3
풀이 접근 방법
- m := 각 단어의 길이, n := target의 길이로 설정합니다.
- d := 크기가 m인 리스트를 만들고, 각 위치(열)별로 문자의 등장 횟수를 저장할 Counter로 초기화합니다.
- words의 각 단어 w에 대해, 각 위치 j의 문자 c마다 d[j][c] 값을 1씩 증가시킵니다. 이렇게 하면 각 열에서 특정 문자가 몇 번 등장하는지 미리 파악할 수 있습니다.
- dfs(i, j) 함수를 정의합니다. 여기서 i는 target에서 지금까지 채운 문자 수, j는 현재 고려 중인 열 인덱스를 의미합니다.
- i가 n과 같으면 target을 모두 완성한 것이므로 1을 반환합니다.
- j가 m과 같으면 더 이상 사용할 수 있는 열이 없으므로 0을 반환합니다.
- (dfs(i, j+1) + dfs(i+1, j+1) × d[j][target[i]]) % (10^9 + 7)을 반환합니다. 첫 번째 항은 j번째 열을 건너뛰는 경우의 수이고, 두 번째 항은 j번째 열에서 target[i]와 일치하는 문자를 선택하는 경우의 수입니다.
- 메인 함수에서 dfs(0, 0)의 결과를 반환합니다.
예제 코드 (Python)
아래 구현을 통해 더 자세히 이해해 보겠습니다.
from collections import Counter
def solve(words, target):
m, n = len(words[0]), len(target)
d = [Counter() for _ in range(m)]
for w in words:
for j, c in enumerate(w):
d[j][c] += 1
def dfs(i, j):
if i == n:
return 1
if j == m:
return 0
return (dfs(i, j + 1) + dfs(i + 1, j + 1) * d[j][target[i]]) % int(1e9 + 7)
return dfs(0, 0)
words = ["pqqp", "qppq"]
target = "qpq"
print(solve(words, target))
효율성 개선 팁
위 재귀 구현은 동일한 상태를 여러 번 반복 계산할 수 있습니다. functools.lru_cache 데코레이터를 dfs 함수에 적용하거나, 2차원 DP 테이블을 사용해 반복문으로 변환하면 시간 복잡도를 O(n × m) 수준으로 크게 줄일 수 있습니다.
입력 및 출력
입력:
words = ["pqqp", "qppq"], target = "qpq"
출력:
4