◾ 단어 퍼즐 : 프로그래머스 LEVEL 4
문제
단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“ba”, “na”, “n”, “a”]인 경우 "ba", "na", "n", "a" 단어 조각이 각각 무한개씩 있습니다. 이때, 만들어야 하는 문장이 “banana”라면 “ba”, “na”, “n”, “a”의 4개를 사용하여 문장을 완성할 수 있지만, “ba”, “na”, “na”의 3개만을 사용해도 “banana”를 완성할 수 있습니다. 사용 가능한 단어 조각들을 담고 있는 배열 strs와 완성해야 하는 문자열 t가 매개변수로 주어질 때, 주어진 문장을 완성하기 위해 사용해야 하는 단어조각 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 주어진 문장을 완성하는 것이 불가능하면 -1을 return 하세요.
입력
- strs는 사용 가능한 단어 조각들이 들어있는 배열로, 길이는 1 이상 100 이하입니다.
- strs의 각 원소는 사용 가능한 단어조각들이 중복 없이 들어있습니다.
- 사용 가능한 단어 조각들은 문자열 형태이며, 모든 단어 조각의 길이는 1 이상 5 이하입니다.
- t는 완성해야 하는 문자열이며 길이는 1 이상 20,000 이하입니다.
- 모든 문자열은 알파벳 소문자로만 이루어져 있습니다.
출력
- 주어진 문장을 완성하기 위해 사용해야 하는 단어조각 개수의 최솟값
- 불가능하면 -1
입출력 예
| strs | t | result |
|---|---|---|
| ["ab", "na", "n", "a", "bn"] | "nabnabn" | 4 |
| ["ba","na","n","a"] | "banana" | 3 |
| ["app","ap","p","l","e","ple","pp"] | "apple" | 2 |
| ["ba","an","nan","ban","n"] | "banana" | -1 |
◾ 풀이
1. 해설
- 참고 : https://dev-note-97.tistory.com/177
- 백트래킹을 사용하여 해결하려 했지만 시간 초과 발생
- 동적 프로그래밍을 활용하여 해결할 수 있었다.
- 각 자리마다 사용할 수 있는 단어 조각이 있는지 확인하고 [앞선 문장 최소값 + 1]을 반복한다.
- 1글자 ~ 5글자에 해당하는 값이 존재하는지 차례로 확인
- j : 단어 시작 인덱스, i : 단어 끝 인덱스(포함X)
- j = 0(i < 5) or i - 5 (각 단어의 길이가 1~5이므로)
- dp[i] = min(dp[j] + 1) (단, t[j:i]에 해당하는 단어가 존재할시)
- 해당 단어를 만들 수 없는 경우 초기값이 유지되어
-1반환
2. 프로그램
- 빠른 탐색을 위해 strs 딕셔너리로 변경
- dp 초기화 : t의 길이가 20000이므로 최대값이 20000이지만, 넉넉하게 100000으로 설정
- t의 길이만큼 차례로 반복하며 단어의 최소값 계산
- j : 탐색 단어 시작 인덱스, i : 탐색 단어 끝 인덱스(포함 X)
- [j:i]에 해당하는 단어가 있는지 확인
dp[j] + 1 < dp[i],t[j:i] in strs- 최소 단어 계산
- 결과 반환
- dp[-1]이 초기값일 경우 : -1
- dp[-1]이 초기값이 아닌 경우 : dp[-1]
# 코드
def solution(strs, t):
answer = 100000
strs = {s : True for s in strs}
t_len = len(t)
dp = [0] + ([100000] * t_len)
for i in range(1, t_len+1):
j = 0 if i < 5 else i - 5
while j < i:
if dp[j] + 1 < dp[i] and t[j:i] in strs:
dp[i] = dp[j] + 1
j += 1
answer = dp[-1] if dp[-1] != 100000 else -1
return answer
후라이드 치킨