(javascript) 알고리즘 - Lv4 단어 퍼즐 (코드별 설명,해석)

문제 설명

단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다.

이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다.

예를 들어 주어진 단어 조각이 [“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 하세요.

 

• 제한사항

1. strs는 사용 가능한 단어 조각들이 들어있는 배열로, 길이는 1 이상 100 이하입니다.
2. strs의 각 원소는 사용 가능한 단어조각들이 중복 없이 들어있습니다.
3. 사용 가능한 단어 조각들은 문자열 형태이며, 모든 단어 조각의 길이는 1 이상 5 이하입니다.
4. t는 완성해야 하는 문자열이며 길이는 1 이상 20,000 이하입니다.
5. 모든 문자열은 알파벳 소문자로만 이루어져 있습니다.

 

• 입출력 예

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

 

---

Solution.js

function solution (strs, t) {
    const tLen = t.length;
    const dp = new Array(tLen).fill(Infinity);
    
    for(let i = 0; i < tLen; i++) {
        //substr() : 문자열에서 특정 위치에서 시작하여 특정 문자 수 만큼의 문자들을 반환
      const current = t.substr(0, i+1);

    
      for(const str of strs) {

        // endsWith() : 문자열에서 특정 문자열로 끝나는지를 확인할 수 있으며, 그 결과를 true 혹은 false로 반환
        if (current.endsWith(str)) {
          const diff = current.length - str.length;
          
          if (diff===0) {
            dp[i] = 1;
          } else {
            dp[i] = Math.min(dp[i], dp[diff-1] + 1);
          }
        }
      }
    }
    return dp[tLen-1] === Infinity ? -1 : dp[tLen-1];
  }

 

문제 풀이

먼저 이 문제를 풀기 위해선 동적 프로그래밍 (DP) 를 사용해야 합니다.

그 이유는 이전에 구한 단어조각(str) 을 통해 다른 새로운 단어조각을 찾을 수 있기 때문인데요,

자세한 내용은 각 코드의 부분별 설명을 통해 이해하 실 수 있을 겁니다.

 

이 코드 풀이에서 주어지는 strs = ["ba","na","n","a"], t = banana 라고 가정하고 설명하겠습니다.

 

1. 먼저 탐색의 기반이되는 DP 배열을 정의해줍니다.

문자열의 크기만큼 반복되기 때문에 DP배열 마찬가지로 문자열과 동일한 크기를 가집니다.

DP 배열의 초기값으로 infinity를 넣어주는데 최솟값을 구하는 것이므로 가장 큰 수를 넣는 것 입니다.

function solution (strs, t) {
    const tLen = t.length;
    const dp = new Array(tLen).fill(Infinity);

 

 

2. substr() 메서드를 이용해 t로 주어지는 문자열을 하나씩 떼어내어 문자열을 구성합니다.

문자열을 한 글자씩 떼어 구성하는 이유는, t라는 문자를 만들기 위한 단어조각 개수가 최솟값이여야 하기 때문에,

다른 단어조각을 통해 더 작은 횟수로 t 라는 문자열을 만들 수 있는지 확인하기 위해서입니다.

그렇기 때문에, 주어진 원소들을 모두 확인하기 위해 1글자 단위로 끊어서 확인합니다.

    for(let i = 0; i < tLen; i++) {
        //substr() : 문자열에서 특정 위치에서 시작하여 특정 문자 수 만큼의 문자들을 반환
      const current = t.substr(0, i+1);

current의 문자열을 출력해보면 다음과 같은 형태를 띕니다.

console.log(current) // -> b, ba, ban, bana, banan, banana

 

 

3. strs 를 참조하는 str를 선언하여 endsWith() 메서드를 이용하여,

current[b, ba, ban, bana, banan, banana] 에서 순서대로 str의 [ba,na,n,a] 중 마지막이 되는 단어 조각을 찾아냅니다

      for(const str of strs) {
        // endsWith() : 문자열에서 특정 문자열로 끝나는지를 확인할 수 있으며, 그 결과를 true 혹은 false로 반환
        if (current.endsWith(str)) {

 

str = ["ba","na","n","a"]

 

순서	current	str의 단어조각이 current의 마지막으로 끝나는 단어조각
1	b	해당하는 단어조각 없음.
2	ba	ba , a
3	ban	n
4	bana	na, a
5	banan	n
6	banana	na, a

• 1번
  해당하는 단어조각이 없기에 카운트 하지 않습니다. 

사용 횟수 : 0

 

• 2번
  ba 와 a 단어조각을 찾았는데 a 단어조각과 b를 사용하면 2회이기 때문에 최솟값인 ba만 사용합니다.

사용 횟수 : 1

 

• 3번
  n 단어조각만 존재하며 ban을 만들기 위해선 2번의 ba에  n을 추가해 ban을 만들 수 있습니다. 1 + 1

사용 횟수 : 2

 

• 4번
  na와 a의 단어조각을 찾았는데 bana를 만들기 위해선 2번의 ba에 na를 추가해 bana를 만들 수 있으며, 3번의 ban과 a를 조합해 만들 수도있습니다.
  만약 2번으로 조합 할 경우  (2번의 사용횟수) 1 + (na) 1 로 총 2회
  만약 3번으로 조합 할 경우  (3번의 사용횟수) 2 + (a) 1 로 총 3회
  따라서 우리는 최솟값을 구할 것이므로

사용 횟수 : 2

 

• 5번
  n 단어조각만 사용할 수 있으며, banan 을 만들기 위해서는 4번의 단어에 현재 단어조각 n을 추가합니다.
  이 때 4번의 사용 횟수는 2 회 이므로 2 + 1 = 3

사용 횟수 : 3

 

• 6번
  4번과 동일하게 na, n 을 사용할 수 있습니다. 
  banana 를 만들기 위해 na 조각을 사용 할 경우 = 4번의 bana를 만들기 위한 사용 횟수 2 + 1 = 3
  banana 를 만들기 위해 a 조각을 사용 할 경우 =  5번의 banan을 만들기 위한 사용 횟수 3 + 1 = 4 가 될 것입니다.
  여기서 3과 4 중 최솟값을 구하면 사용 횟수는

사용 횟수 : 3

 

이 과정을 보면 이 전의 구한 부분 문제를 통해 큰 문제를 해결 하는 것을 볼 수 있습니다.

이를 통해 왜 DP를 사용해야하고 DP가 적용되는 지 알 수 있습니다.

 

여기까지 값을 구했을 떄, dp의 배열을 1부터 6번까지 순서대로 확인해 보면 다음과 같습니다. console.log(dp)

[ Infinity, Infinity, Infinity, Infinity, Infinity, Infinity ]
[ Infinity, 1, Infinity, Infinity, Infinity, Infinity ]
[ Infinity, 1, Infinity, Infinity, Infinity, Infinity ]
[ Infinity, 1, 2, Infinity, Infinity, Infinity ]
[ Infinity, 1, 2, 2, Infinity, Infinity ]
[ Infinity, 1, 2, 2, Infinity, Infinity ]
[ Infinity, 1, 2, 2, 3, Infinity ]
[ Infinity, 1, 2, 2, 3, 3 ]

 

3. diff 라는 변수를 선언해 current 변수의 길이와 str 변수의 길이의 차를 구합니다.

만약 diff 가 0일 이 일치한다는 것을 의미하므로 해당 조각을 1번 사용해 만들 수 있음을 의미합니다.

그렇지 않을 시, dp 점화식을 사용하여 최소값을 구합니다.

dp 점화식
dp[i] = Math.min(dp[i], dp[현재 문자열 길이 - 단어조각 길이] + 1)
=> 각 단계는 이전 단계에서 사용한 횟수를 얻어와서 현재 단어조각의 사용 횟수인 1을 더해주는 것을 볼 수 있습니다.
그러므로 dp[현재 문자열 길이 - 단어조각 길이] 로 구한 최솟값에 1을 더합니다.

        if (current.endsWith(str)) {
          const diff = current.length - str.length;
          
          // 둘의 차가 0이라는 것은 서로 완벽히 일치함을 의미
      	  // 즉 해당 조각을 1번 사용하는 것으로 지금 문자열 완성 가능
          if (diff===0) {
            dp[i] = 1;
          // 길이가 다를 시 dp 점화식 사용
          } else {
            dp[i] = Math.min(dp[i], dp[diff-1] + 1);
          }
}

 

4. 정답은 dp 배열의 가장 마지막에 있으므로 해당 위치의 원소가 infinity 라면 문자열을 만들수 없음을 의미하므로 -1을 리턴하고 아닐시 해당 원소의 마지막인 dp[tLen-1]을 리턴합니다.

    return dp[tLen-1] === Infinity ? -1 : dp[tLen-1];

---

참고자료
https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.4-%EB%8B%A8%EC%96%B4-%ED%8D%BC%EC%A6%90