[4주차 - Sorting & Dynamic Programming] 단어퍼즐

본 포스팅은 프로그래머스에서 진행하는 코딩테스트와 실무역량 모두 잡는 알고리즘 스터디(Python반) 6기에 참여 하면서 공부한 내용을 정리한 것이다. (https://programmers.co.kr/learn/courses/12441)

 

상단부터 

1. [문제설명] 
2. [문제풀이] 
3. [코드 리뷰를 통해 발견한 개선할 점] 
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 이하입니다.
• 모든 문자열은 알파벳 소문자로만 이루어져 있습니다.

---

 

입출력 예

strstresult

["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 합니다.

---

[문제풀이]

4주 차 주제 가운데 하나가 동적계획법이다. 하지만 동적 계획법에 대한 경험이 많이 부족한 상태에서 풀어야 했는데 처음 시도했던 것은 재귀 호출을 사용한 top down식 풀이다.

def get_w_cnt(strs, t, cnt, cnts):
    if t in strs:
        cnts.append(cnt + 1)
        return

    # t의 후미부터 슬라이싱한 문자열이 strs에 있는지 확인하여 있으면 재귀호출
    for i in range(len(t) - 1, -1, -1):
        if t[i:] in strs:
            get_w_cnt(strs, t[:i], cnt + 1, cnts)

    try:
        return min(cnts)
    except ValueError:
        return -1


def solution(strs, t):
    return get_w_cnt(set(strs), t, 0, list())

제출 시 최대 재귀 깊이 초과로 런타임 에러가 뜨고 엣지 케이스를 모두 잡지 못했으며 효율성 검사도 통과하지 못했다.

---

[코드 리뷰를 통해 개선할 점]

1. 재귀 호출을 사용한 top down대신 bottom up 즉 반복문을 사용한 동적계획법을 적용하여 풀어 보기를 권장

 

처음에는 어떻게 재귀를 반복문으로 풀어낼지 감이 오지 않아, 스터디 리더의 도움을 받았다. 하나의 입력 예로 아이디어를 정리하면 다음과 같다.

 

먼저 주어진 입력이 다음과 같을 때

t = "apple"
strs = ["app", "ap", "p", "l", "e", "ple", "pp"]

다음과 같이 문자열 t의 길이와 동일한 길이의 dp 리스트를 만들고 모든 요소를 무한대로 설정한다.

inf = int(1e9)

dp = [inf] * len(t)

index 4 부터 시작하는 각각의 부분 문자열들이 strs에 존재하는지 확인한다.

strs에서 찾을 문자열: t[4:5] => 'e'
'e' 를 strs에서 찾는다.
    찾았다. 'e'까지 만드는데 드는 최저 조각 수는 e = 1개이다. 따라서 dp[4] = 1 이다.

index 3 부터 시작하는 각각의 부분 문자열들이 strs에 존재하는지 확인한다.

strs에서 찾을 문자열: t[3:5] => 'le'를 strs에서 찾는다.
    없으니 아무것도 하지 않는다.
strs에서 찾을 문자열: t[3:4] => 'l'을 strs에서 찾는다.
    찾았다. l로 시작하여 le까지 만드는데 드는 최저 퍼즐 수는
    l + e = 2개이다. 따라서 dp[3] = 2 이다.

index 2 부터 시작하는 각각의 부분 문자열들이 strs에 존재하는지 확인한다.

strs에서 찾을 문자열: t[2:5] => 'ple'를 strs에서 찾는다.
    찾았다. ple로 시작하여 ple를 만드는데 드는 최저 조각 수는
    ple = 1개이다. 따라서 dp[2] = 1 이다.
strs에서 찾을 문자열: t[2:4] => 'pl'을 strs에서 찾는다.
    없으니 아무것도 하지 않는다.
strs에서 찾을 문자열: t[2:3] => 'p'를 strs에서 찾는다.
    찾았다. p로 시작하여 ple를 만드는데 드는 최저 조각 수는
    p + l + e = 3개이다.
    하지만 이미 dp[2] = 1 즉, ple를 만드는데 드는 최저 조각 수가 1이므로

    dp 리스트를 업데이트하지 않는다.

index 1 부터 시작하는 각각의 부분 문자열들이 strs에 존재하는지 확인한다.

strs에서 찾을 문자열: t[1:5] => 'pple'를 strs에서 찾는다.
    없으니 아무것도 하지 않는다.
strs에서 찾을 문자열: t[1:4] => 'ppl'를 strs에서 찾는다.
    없으니 아무것도 하지 않는다.
strs에서 찾을 문자열: t[1:3] => 'pp'를 strs에서 찾는다.
    찾았다. pp로 시작하여 pple를 만드는데 드는 최소 퍼즐 개수는
    pp + l + e = 3개이다. 현재 index 1에서 시작할 수 있는
    최저 퍼즐 개수는 3이 된다. 따라서 dp[1] = 3이다.
strs에서 찾을 문자열: t[1:2] => 'p'를 strs에서 찾는다.
    찾았다. p를 첫 번째 조각으로 하여 pple를 만들 수 있는 최소 퍼즐 개수는
    p + ple = 2개이다. 따라서 index 1에서 시작할 수 있는 최소 퍼즐 개수는
    2 이므로 기존의 dp[1] 값을 3에서 2로 업데이트 한다.

index 0 부터 시작하는 각각의 부분 문자열들이 strs에 존재하는지 확인한다.

strs에서 찾을 문자열: t[0:5] => 'apple'를 strs에서 찾는다.
    없으니 아무것도 하지 않는다.
strs에서 찾을 문자열: t[0:4] => 'appl'를 strs에서 찾는다.
    없으니 아무것도 하지 않는다.
strs에서 찾을 문자열: t[0:3] => 'app'를 strs에서 찾는다.
    찾았다. app를 첫 번째 조각으로 하여 le를 만드는 최소 퍼즐 개수는
    app + l + e = 3개이다. 따라서 dp[0] = 3이다.
strs에서 찾을 문자열: t[0:2] => 'ap'를 strs에서 찾는다.
    찾았다. ap를 첫 번째 조각으로 하여 ple를 만드는 최소 퍼즐 개수는
    app + ple = 2개이다. 따라서 dp[0]의 값을 3에서 2로 변경한다.
a를 strs에서 찾는다.
    없으니 아무것도 하지 않는다.

 

결국 dp[0]의 값이 찾는 답이 된다.

 

 

위의 내용을 다음과 같이 구현했다.

def solution(strs, t):
    inf = int(1e9)
    strs_set = set(strs)
    dp = [inf for _ in range(len(t))]

    for lp in range(len(t) - 1, -1, -1):
        # for rp in range(min(len(t), 6), 0, -1):
        for rp in range(len(t), 0, -1):
            if t[lp:rp] in strs_set:
                # rp == len(t) 즉 부분문자열 전체가 한 번에 일치하는 것이면 dp[lp]를 구성하는 퍼즐은 한조각이라는 말이다.
                # 따라서 dp 테이블의 해당 index의 값을 1로 변경한다.
                if rp == len(t):
                    dp[lp] = 1
                # rp < len(t)이면 부분 문자열은 2개 이상의 퍼즐 조각으로 구성된 경우이다. 여러 조합들 가운데 최소의 조각을
                # 소비하는 조합을 찾아낸다.
                else:
                    # dp[lp]: 현재 index에서 시작하여 조합할 수 있는 최저 퍼즐 수량
                    # dp[rp]: 다음 퍼즐 조각이 시작되는 위치의 현재 최저 퍼즐 수량
                    # t[lp:rp]를 하나의 조각으로 보고 t[rp:]를 구성하는 최저 퍼즐 수량에 더한 수량이 dp[lp]보다 작으면
                    # dp[lp]를 업데이트 해준다.
                    dp[lp] = min(dp[lp], dp[rp] + 1)

    return dp[0] if dp[0] != inf else -1

하지만 위의 코드를 판정해보면 시간초과가 발생했는데, 그 원인은 모든 단어의 길이는 1 ~ 5라는 제한사항을 고려하지 않고 작성했기 때문이다. t를 슬라이싱 하여 부분문자열을 만들어낼 때 maximum length가 5 이하의 자연수가 되도록 수정하여 해결했다.

---

[코드리뷰 완료 후 전체 코드]

def solution(strs, t):
    inf = int(1e9)
    strs = set(strs)
    dp = [inf for _ in range(len(t))]
    for lp in range(len(t) - 1, -1, -1):
        sub_s_len = len(t) - lp # lp로 부터 시작하는 가장 긴 문자열의 길이
        # 부분 문자열의 오른쪽 끝에서 부터 하나씩 줄여가며 strs에 부분문자열이 있는지 확인한다.
        # 단 부분문자열의 길이가 5를 초과하는 경우, 비교하는 문자열은 t[lp:lp + 1] ~ t[lp:lp + 6]으로 한다.
        for i in range(min(5, sub_s_len), 0, -1):
            rp = lp + i
            if t[lp:rp] in strs:
                # rp == len(t) 즉 부분문자열 전체가 한 번에 일치하는 것이면 dp[lp]를 구성하는 퍼즐은 한조각이라는 말이다.
                # 따라서 dp 테이블의 해당 index의 값을 1로 변경한다.
                if rp == len(t):
                    dp[lp] = 1
                # rp < len(t)이면 부분 문자열은 2개 이상의 퍼즐 조각으로 구성된 경우이다. 여러 조합들 가운데 최소의 조각을
                # 소비하는 조합을 찾아낸다.
                else:
                    # dp[lp]: 현재 index에서 시작하여 조합할 수 있는 최저 퍼즐 수량
                    # dp[rp]: 다음 퍼즐 조각이 시작되는 위치의 현재 최저 퍼즐 수량
                    # t[lp:rp]를 하나의 조각으로 보고 t[rp:]를 구성하는 최저 퍼즐 수량에 더한 수량이 dp[lp]보다 작으면
                    # dp[lp]를 업데이트 해준다.
                    dp[lp] = min(dp[lp], dp[rp] + 1)

    return dp[0] if dp[0] != inf else -1