23.06.06 파이썬 코딩 퀴즈#247 단어 퍼즐 (프로그래머스 스쿨)

단순하게 보면 굉장히 쉬운 문제처럼 보인다.

주어진 strs 를 이용하여 목표 문자열 t를 만드는데, 최소한의 strs 만 사용해야 한다. 위 설명처럼 같은 문자열을 중복해서 사용 가능하며, strs 안에는 중복된 문자열은 주어지지 않는다.

만약, 주어진 strs 로 t를 만들수 없는 경우라면 -1를 반환하면 된다.

문제는 굉장히 심플한 문제인데, 생각보다 어려운 문제이다.

 

str.replace를 사용하는 경우

replace를 이용하여 단어들을 한번씩 변환하는 경우에는 strs 에 주어진 단어중에 어떤 단어를 먼저 선택할 것인지에서 문제가 생긴다.

["ab", "na", "n", "a", "bn"], "nabnabn" 로 전달받은 경우, 정답은 4 이다.

하지만 4번만에 해당 단어를 만들기 위해서는 먼저 bn 을 2번 사용해야 하고, na을 한번 그리고 a를 사용해야 한다.

하지만 위 순서대로 사용하지 않고, 해당 단어들을 무조건 relace를 통해 갱신하게 된다면 5번에 가능하다.

 

DP를 이용하는 경우

해당 문제가 DP 문제인지 아니면 BFS DFS 문제인지는 알길이 없다.

하지만 전달받은 t를 음절 단위로 확인하면서 DP로 최소값을 입력해가며 풀이를 해보면 좋을 듯 하다.

레벨에 맞지 않게 코드는 굉장히 간결하다.

처음에는 시간초과 때문에 너무 머리가 아팠는데, 알고보니 문제의 핵심은 strs 의 요소의 길이가 1~5라는 것에 있었다.

즉 이중 반복문을 통해 시작점 start(i) 와 end 를 설정한 다음, t의 부분 문자열 target (t[start:end]) 를 확인하면서

만약 strs 에 target이 존재하는 경우라면, dp 배열의 [end]에 최소값을 확인하고 갱신하는 방식이다.

입출력 예 1번을 위 코드로 작성해보면 

dp 는 최종적으로 [0, inf, 1, inf, 2, inf, 3] 이 된다.

먼저 i 가 0인 경우를 살펴보자. 

target 은 t[0:1] ~ t[0:5] 까지 가능하며, 이때 target이 "ba"가 되는 경우에 dp 값이 갱신된다.

그리고 비교되는 값은 dp[0]+1 과 dp[2] 이므로, dp[2] 는 0+1 이 된다.

 

그 다음 i 가 1이 되는데,

여기에서는 'a' 인 경우 t[1:2] 만 해당된다.

따라서 dp[2] = min(dp[1]+1, dp[2]) 이므로 dp[2] 값을 유지하게 된다.

 

위와같은 순서로 탐색을 하게 되면 최종적으로 dp[-1] 값이 단어 퍼즐을 완성하는 최소값이 된다.