[JavaScript] 단어퍼즐 : 주어진 단어 조각들을 최소로 이용하여 주어진 문장을 완성하기

 🔍 자바스크립트 알고리즘 문제07. 단어퍼즐 : 주어진 단어 조각들을 최소로 이용하여 주어진 문장을 완성하기

 

코드 기획

1️⃣ DP(Dynamic Programming) 이용하기 : 다이나믹 프로그래밍이란 큰 문제를 작은 문제로 쪼개서 푸는 기법으로, 한 번 계산 한 값을 저장하여 중복 계산을 줄이는 방식입니다. 처음에 코드 예제를 가시화하여 반복되는 부분을 찾던 중 재귀호출을 이용하면 될 것이라고 생각했으나 모든 조합을 시도해보며 정답을 찾는 재귀호출보다는 더 효율적인 다이나믹 프로그래밍 방식을 차용하기로 결정했습니다.

 

코드 작성

function solution(strs, t){
    const INF = Infinity;
    let dp = new Array(t.length+1).fill(INF);
    dp[0] = 0;
    
    for(let index = 0; index < t.length; index++){
        //여기까지 짤랐을 때의 값이 무한=갱신된 값이 없다면 그냥 통과하고 지나가도 됨
        if(dp[index] === INF) continue;
        
        //(자바스크립트 개념)for..in은 객체일 때, for..of는 배열일 때 주로 사용
        //strs 배열 내에 있는 값들을 비교하기
        for(let str of strs){ 
            let nextIndex = j + str.length;
            //조건1번 : 다음 인덱스(다음길이)가 총 문자열의 길이를 넘으면 안됨
            //조건2번 : 뒤에 내용도 일치하는지 확인 -> 뜯어와서 확인
            if(nextIndex <=t.length && t.substring(j,nextIndex) === str){
                dp[nextIndex] = Math.min(dp[nextIndex],dp[j]+1);
                //무한으로 채워야하는 이유 : 초기값이 올바르게 들어가기 위해서는 필요
            }
        }
    }
    //주어진 문자열로 구성할 수가 없어서 최종 값이 변화없이 무한이라면 -1을 출력함
    return dp[t.length] === INF? -1: dp[t.length];
}

1️⃣ Infinity는 무한대를 나타내는 특수한 숫자 값으로, 상수로 숫자타입으로 양의 무한대고 -Infinity는 음의 무한대를 의미합니다. 위의 주석에서도 언급했지만, dp[] 배열의 완전한 초기값으로 무한대를 넣어주는 이유는 진짜 초기값으로 부를 수 있는 값보다 언제나 커야하기 때문에 그렇습니다.

 

2️⃣ dp[i]는 문자열 t에서 [0:i]까지 만들기 위해 필요한 최소 단어 조각 개수를 의미합니다. 그러기 때문에 값을 갱신할 때  dp[nextIndex]와 dp[j]+1이 비교대상으로 들어가게 되는 것입니다. for문(for...of문 위에 나온 반복문) 아래에 조건으로 걸린 것은 그곳까지 갈 수 있는 문자열이 없기 때문에 continue 키워드를 사용하여 다시 조건으로 돌아가게 됩니다. 

 

3️⃣ 처음에 이 알고리즘을 작성하고 수정 후 해석해보면서 어려웠던 부분이 많았기 때문에 문제에서 제공해준 예제로 시각화하여 보겠습니다. 

strs = ["ab","na","n","a","bn"] / t = "nabnabn"

j=0 "n"-> dp[1] = 1("n") / dp[2] = 1("na")
j=1 "a"-> dp[2] = Math.min(2("n"-"a"),1) = 1("na") / dp[3] = 2("n"-"ab")
j=2 "b"-> dp[4] = 2("na"-"bn")
j=3 "n"-> dp[4] = Math.min(3("n"-"ab"-"n"),2) = 2("na"-"bn") / dp[5] = 3("n"-"ab"-"na")
j=4 "a"-> dp[5] = Math.min(3, 3("na"-"bn"-"a")) = 3/ {dp[6] = 무한대로 이프문에서 continue}
j=5 "b"-> dp[7] = 4("na"-"bn"-"a"-"bn")
j=6 "n"-> dp[7] = 4 /{dp[8] = 총길이를 넘었으므로 끝}

 

배운 점

- 다이나믹 프로그래밍( DP)이란 한 번 계산 한 값을 저장하여 중복 계산을 줄이는 알고리즘 기법입니다.

- 자바스크립트에서 양의 무한대로 최소값이나 최댓값을 비교할 때는 Infinity 키워드를 써야합니다.