문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/12983
문제 유형
DP
🌈 문제
단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“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 이하입니다.
- 모든 문자열은 알파벳 소문자로만 이루어져 있습니다.
입력
strs : ["ba","na","n","a"],
t: "banana"출력
3💡 아이디어
순열을 이용하여 모든 문자열을 조합해 볼 수 있을 것 같기도 하고, 백트래킹으로 모든 문자열을 탐색하면서 조건에 맞지 않는 문자열이 등장한다면 더이상 탐색하지 않고 새로운 노드를 탐색하는 방식으로 풀이할 수 있을 것처럼 보인다. 그러나, 이 문제는 DP로 풀어야 시간 복잡도 문제를 통과할 수 있다.
그러므로, DP의 규칙성으로 풀 수 있는 문제인가?를 꼼꼼히 되짚어 보면서 풀이의 실마리를 잡아야 한다. 가장 작은 단위로 먼저 쪼개는 것이 DP의 기본이므로, banana를 기준으로 생각해 보았을 때, ba 를 만들 수 있는 단어 개수의 최솟값을 따져보고, 더 나아가 ban의 최소 개수, bana의 최소 개수를 점진적으로 따져 보아야 한다.
이렇게 최소 개수를 점진적으로 구하다 보면 결국 우리가 원하는 큰 단체인 banana에 대한 최소값이 성립하는지 확인해야 한다. 위의 예시로 주어진 입출력에서는 ba를 만들기 위해 최소 1개의 단어 조각으로 만들 수 있고, ban은 ["ba", "n"]으로 나누어질 수 밖에 없는 구조이다. 그런데, ba는 이미 1로 알고 있기 때문에 n에 대한 수 1만 저장하면 된다. 그러니 ban을 만드는 단어 조각은 최소 2이다.
bana를 따져 보자. ["b", "ana"], ["ba", "na"], ["ban", "a"]로 나눌 수 있고, 허용되는 것은 ["ba", "na"]이다. 앞서 ba는 이미 1임을 구했고, na또한 1이기 때문에 bana는 단어 개수 최솟값이 2가 됩니다.
이런식으로 가장 큰 단위인 banana를 확인해 보자. ["bana", "na"]와 ["banan", "n"]입니다. ["bana", "na"]은 각각 2와 1이 더해져 3이지만 ["banan", "n"]은 3과 1이 더해져 4기 때문에 저 작은 값인 ["bana", "na"]을 선택 가능함을 알 수 있다.
이렇게 동적 계획법으로 문제를 풀이할 수 있다! 이제 파이썬으로 코드를 작성해보자.
👨💻 코드 작성
import sys
def solution(strs, t):
max_int = sys.maxsize
answer = 0
dp = [0 for _ in range(len(t) + 1)]
#문자열 검사를 빠르게 하기 위하여 문자열 리스트를 set으로 변경한다.
setstrs = set(strs)
for i in range(1, len(t) + 1):
dp[i] = max_int
#단어조각은 5조각 이하이기 때문에 그 이상 자를 필요 없다.
for j in range(1, min(i + 1, 6)):
start = i - j;
end = i
if(t[start:end] in setstrs):
dp[i] = min(dp[i], dp[i-j] + 1)
if dp[-1] == max_int:
return -1
else:
return dp[-1]
이렇게 코드를 작성할 수 있다. 그 전의 잘라진 조각들을 이용할 수 있도록 i-j번 인덱스부터 검사하여 분할하는 것이다.
dp[2]를 검사할 때는 [a, p], [ap] 이렇게 나누어 볼 수 있고, dp[3]는 [app, l], [a, pp], [app] 로 나누어 최소값을 dp[3] = 1 로 잡아 볼 수 있는 것이다.
최종적으로 ["app","ap","p","l","e","ple","pp"] 과 "apple"의 dP배열은
[0, INF, 1, 1, 2, 2]로 결정되어 dp[5]인 2가 답으로 도출되는 것이다.
