프로그래머스 LEVEL 4(단어 퍼즐)

사용 언어 : javascript
해결 날짜 : 2022-10-25
해결 방법 :
- dp로 해결
- 각 자릿수 별 최소 값을 저장하기 위해 dp Infitiy로 초기화
- 입력받은 문자열 t를 돌며 현재 인덱스까지 자른 current
- current가 strs 속 단어 조각으로 끝나는 경우, dp 업데이트
  - 이 때 현재 단어 조각의 자릿수 만큼 뺀 인덱스의 dp값 + 1과, 현재 인덱스의 dp값을 비교하여 작은 값으로 업데이트
- dp의 마지막 인덱스의 값을 반환하되, Infinity인지 체크하여 Infinity인 경우 만들 수 없는 경우이므로 -1 반환
회고 :
- 처음에 당연히 2차원 배열로 방문 여부를 체크하여 풀려고 했는데 더 간단한 방법이 있었다.
- 천천히 풀이 방법 생각하고 풀기..

코드

function solution(strs, t) {
    const dp = Array.from({length: t.length}, () => Infinity);

    for (let i = 0; i < t.length; i++) {
        const current = t.slice(0, i + 1);
            
        for (const str of strs) {
            if (current.endsWith(str)) {
                const start = i - str.length;
                if (start === -1) dp[i] = 1;
                else dp[i] = Math.min(dp[i], dp[start] + 1);
            }
        }
    }
        
    return dp[dp.length - 1] === Infinity ? -1 : dp[dp.length - 1];
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges