단어 퍼즐 ( Level 4, JavaScript, 2017 팁스타운 )

단어 퍼즐 ( Level 4 )

Programmers 2017 팁스타운 ( JavaScript )

문제 링크

 

나의 풀이

function solution(strs, t) {
    const dp = Array(t.length + 1).fill(20001);
    const longest = strs.sort((a,b) => b.length - a.length)[0].length;
    dp[0] = 0
    for ( let i = 1; i < dp.length; i++ ) {
        for ( let j = i; j >= Math.max(0, i-longest); j-- ) {
            const start = j === 0 ? 0 : j - 1;
            if ( strs.includes(t.slice(start,i)) ) {
                dp[i] = Math.min(dp[i], dp[start]+1)
            }
        }
    }
    return dp.slice(-1)[0] === 20001 ? -1 : dp.slice(-1)[0]
}

1. dp에 t의 길이 + 1 만큼의 배열을 만들고 20001로 채운다. ( t의 최대 길이는 20000이기 때문)
2. longest에 str중 가장 긴 문자열의 길이를 담는다
3. dp 0 번째 요소를 0으로 초기화한다
4. 그 다음 포문은 예시로 설명
   1. t 가 abcde 라 하자.
   2. 이 때 t.slice(start, i) 는 a, b, ab, c, bc, abc... 와 같이 대입된다.
5. 포문이 진행되면서 dp에 누적 문자열 조합 중 최소 개수를 대입하며 마지막까지 연산 후 마지막 요소를 확인해 str로 조합이 불가능하면 -1 나머지 경우는 최소값인 마지막 값을 리턴한다.