[프로그래머스] 단어 퍼즐

Об этом предложении

문제 요약 주어진 단어 조각을 원하는 만큼 사용해 문자열 t 를 완성한다. 문자열을 완성하는 데 필요한 단어 조각 수의 최솟값을 구하고, 만들 수 없다면 -1 을 반환한다. 핵심 아이디어 dp[i] 를 t 의 앞에서부터 i 글자까지 완성하는 데 필요한 최소 조각 수라고 정의한다. dp[0] = 0 어떤 위치 i 까지 만들 수 있고, 그 위치부터 시작하는 조각 piece 가 t 와 일치한다면 다음 위치를 갱신한다. dp[i + len(piece)] = min( dp[i + len(piece)], dp[i] + 1 ) 각 조각을 무한히 사용할 수 있으므로, 같은 조각을 여러 위치에서 반복해서 사용해도 된다. 풀이 과정 길이가 len(t) + 1 인 DP 배열을 만들고, 도달할 수 없는 값은 큰 값으로 초기화한다. dp[0] = 0 으로 시작한다. 문자열의 각 위치에서, 해당 위치부터 일치하는 모든 단어 조각을 확인한다. 일치하는 조각의 끝 위치를 최소 조각 수로 갱신한다. dp[len(t)] 가 여전히 큰 값이면 -1 을 반환한다. Python 코드 def solution(strs, t): length = len(t) infinity = length + 1 # dp[i]: t의 앞 i글자를 만드는 데 필요한 최소 조각 수 dp = [infinity] * (length + 1) dp[0] = 0 for start in range(length): if dp[start] == infinity: continue for piece in strs: end = start + len(piece) if end <= length and t.startswith(piece, start): dp[end] = min(dp[end], dp[start] + 1) return -1 if dp[length] == infinity else dp[length] 예시 strs = ["ba", "na", "n", "a"] , t = "banana" 인 경우를 보자. dp[0] = 0 "ba" 사용 -> dp[2] = 1 "na" 사용 -> dp[4] = 2 "na" 사용 -> dp[6] = 3 따라서 "ba" + "na" + "na" 로 문자열을 만들 수 있고, 필요한 조각 수는 3 이다. 시간 복잡도 N 을 t 의 길이, S 를 단어 조각 개수, L 을 조각의 최대 길이라고 하자. 각 위치에서 모든 조각을 확인하고, 문자열 비교는 최대 L 글자를 확인한다. 시간 복잡도: O(N * S * L) 공간 복잡도: O(N) 이 문제에서는 N <= 20,000 , S <= 100 , L <= 5 이므로 충분히 빠르게 동작한다. 정리 문자열을 앞에서부터 완성하는 최소 비용 문제로 바꾸면 된다. dp[i] 가 도달 가능한 위치인지 확인하고, 그 위치에 이어 붙일 수 있는 단어 조각으로 다음 상태를 갱신한다.

Детали предложения

Провайдер

velog

Источник

velog-rss

Балл

54.39

Уверенность

49%