2017_탑스다운_#3. 단어 퍼즐

코딩 테스트 연습 - 단어 퍼즐 | 프로그래머스 (programmers.co.kr)

단어 퍼즐

문제 설명

단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“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                                                                                                              t                                           result

["ba","na","n","a"]	"banana"	3
["app","ap","p","l","e","ple","pp"]	"apple"	2
["ba","an","nan","ban","n"]	"banana"	-1

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
"ap" 1개, "ple" 1개의 총 2개로 "apple"을 만들 수 있으므로 필요한 단어 개수의 최솟값은 2를 return 합니다.

입출력 예 #3
주어진 단어로는 "banana"를 만들 수 없으므로 -1을 return 합니다.

 

---

( 문제 해결 알고리즘 )

strs로 주어지는 배열의 길이는 최대 5개 최소 1개 입니다.

t로 주어진 target 단어의 길이만큼 dp로 풀어볼 수 있습니다.

strs은 중복되는 단어는 불필요하므로 set을 써서 처리합니다.

1. 일단 dp [0 [ = 0 은 0이라고 가정합니다. 주어진 str로 t를 맞추기 위해 아무것도 안 쓴다는 의미입니다.

 

2. 1부터 strs 중 단어를 써서 맞추는 최소의 경우로 dp를 최신화할 것입니다.

 

3. 그럼 1부터 len(t) + 1만큼 for문을 순회합니다. => for i in range(1, n + 1):

 

4. 우리가 하려는 건 st = 0으로 시작해서 i를 끝으로 t [st : i]가 strs에 있으면 dp를 최신화하려고 합니다.

따라서 그에 따른 로직을 짜야합니다.

(힌트) 최대 strs길이 5

(힌트) 0을 시작으로 i만큼 한 칸씩 늘리면서 strs가 있는지 탐색할 것

 

5. 힌트의 생각을 기반으로 코드를 짜 봐야 합니다.

현재의 시점으로 최대 5만큼만 탐색하면 되겠죠 => for k in range(1, 6):

그리고 탐색하는 구간이 strs에 있으면 dp를 최신화할 것입니다.

if t [k : i] in strs:

이렇게 표현할 수 있을 것(?) 같습니다. 다만 문제가 있는데

네 맞습니다. k가 i보다 커지는 상황이 발생합니다.

우리가 원하는 상황은 ( i가 3이라면)

[2:3], [1:3], [0:3] 이렇게 탐색을 원하는 것입니다.

근데 t [k: i]를 하면 문제가 되겠죠.

k에 대한 처리가 필요해 보입니다.

 

6. i보다 커지면 안 되므로 일단 i를 써봅시다. 그러고 나서 k가 커지는 방식이므로 i - k를 하면 우리가 원하는 형식으로 간격이 벌어지면서 탐색을 할 듯합니다.

단, 음수는 필요 없으므로 i - k < 0 일 때 0으로 할 필요가 있어 보입니다.

if t [i - k:i] in strs: 단 i - k < 0 이면 i - k = 0 이렇게 하면 되겠네요 

그러면 자연스럽게 dp 식은 dp [i] = min(dp[i], dp[i - k] + 1) 이 되겠죠?

i - k 간격만큼 탐색해보니 sts에 값이 있다면 i - k에서 찾은 dp값 + 1과 비교하여 min값을 최신화하면 될 것 같습니다.

이제 이것을 코드로 풀면 됩니다.

 

---

[코드]

 

def solution(strs, t):
    n = len(t)
    dp = [float('inf')] * (n + 1)
    strs = set(strs)
    # dp[1] 은 문자열 하나의 조합으로 최소값 리턴
    # 즉, dp[0] 문자열을 안쓴다는 의미가 되므로 0이라고 한 것
    dp[0] = 0
    
    # 1 ~ n 까지만큼 dp 최신화를 할거임
    for i in range(1, n + 1):
        for k in range(1, 6):
            # i까지 그리고 i - (최대 단어 조합 길이) 까지 순회하면서 dp 최신화
            if i - k < 0:
                s = 0
            else:  # i - k >= 0
                s = i - k
            # 해당 범위가 strs 조합목록에 있으면
            if t[s:i] in strs:
                # dp 최신화
                dp[i] = min(dp[i], dp[i - k] + 1)
                
    if dp[-1] == float('inf'):
        answer = -1
    else:
        answer = dp[-1]

    return answer

---

후기

 

어렵네요.

어렵습니다.

연습이 필요할 듯싶네요