[프로그래머스] LV.4 단어 퍼즐

KG·2021년 6월 17일

알고리즘

목록 보기

57/61

문제

단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“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 이하입니다.
모든 문자열은 알파벳 소문자로만 이루어져 있습니다.

입출력 예시

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

풀이

난이도 Lv.4의 문제이기 때문에 일반적인 접근 방법으로 문제를 해결하려고 하면 당연히 정상적으로 통과할 수 없을 것이다. 여기서 일반적인 방법이라 함은, 주어진 strs 배열의 각 원소를 가지고 t라는 문자열을 완성하기 위해 차례대로 순회하며 사용한 원소 개수를 카운트하는 방법일 것이다. 주어진 각 원소는 무한개 존재한다고 되어있기 때문에 해당 방식은 시간 복잡도가 매우 높다는 것이 자명하다. 따라서 어떤 접근 방식을 통해 해당 문제를 풀이할지 하나씩 살펴보도록 하자.

1) 문자열 결합형태

t에 주어지는 문자열을 하나씩 떼어내서 생각해보자. 예를 들어 banana의 경우 앞에서부터 차례대로 문자열을 구성시킨다고 생각하면 다음과 같이 6번의 형태가 있을 것이다.

b
ba
ban
bana
banan
banana

위와 같이 한 글자씩 차례대로 생성 순서를 나열하는 이유는, strs에 주어지는 각 원소들의 단위가 최소 1글자에서 5글자 사이의 크기를 가지기 때문이다. 주어진 원소들의 나열을 통해 t 라는 문자열을 만들 수 있다고 하더라도, 우리가 구해야 할 것은 만들기 위한 단어조각 개수의 최솟값이기 때문에 다른 단어조각을 통해 더 작은 횟수로 t 라는 문자열을 만들 수 있는지 확인해야 한다. 때문에 주어진 원소들을 모두 확인하기 위해서 1글자 단위로 끊어서 살펴볼 것이다.

위에서 나열한 6가지 문자열의 형태를 일련의 결합형태라고 하겠다. 각각의 결합형태를 구성하기 위해 필요한 단어조각은 다음과 같이 나타낼 수 있을 것이다.

b : b
ba : b/a 또는 ba
ban : b/a/n 또는 ba/n 또는 ban
bana : b/a/n/a 또는 ba/n/a 또는 bana
...

물론 위의 예시 외에도 더 많은 조합이 존재한다. 예를 들어 4번 결합형태의 경우에는 ba/na 단어조각으로 만들 수 있고, 이 경우가 ba/n/a 처럼 3개의 조각을 쓰는 경우보다 더 적은 조각을 쓰기에 최솟값이 될 가능성이 높다.

하지만 우리가 주목해야할 점은 다음의 패턴이다. 자세히 보면 뒤에 위치한 결합형태의 필요조각을 판단하는 부분에서 이전에 사용한 조각을 재사용하고 있음을 알 수 있다. 가령 2번과 3번의 결합형태를 보자면, 2번에서는 b/a 2개의 단어조각과 ba 1개의 단어조각을 사용하고 있음을 알 수 있다. 그리고 이윽고 3번 결합형태에서는 기존 b/a 조각에 추가로 한 개의 n 조각이 추가되었고, 마찬가지로 ba 조각에도 n 조각이 추가되고 있음을 알 수 있다.

이처럼 이전에 사용한 패턴을 재사용하기 위한 알고리즘으로 떠올릴 수 있는 것은 DP 알고리즘이다. 따라서 우리는 DP 알고리즘을 해당 문제에 적용시켜 풀어볼 것이다.

2) 각 문자열 결합형태와 단어조각의 상관관계

그렇다면 해당 문제를 어떻게 DP 알고리즘을 잘 적용시켜 점화식을 찾아낼 수 있을지 고민해보자. 위의 예시에서 전에 사용한 패턴을 그대로 가져와 추가적인 작업을 하고 있음은 이미 살펴보았다. 그렇지만 문제에서 주어지는 strs 배열에는 위 경우처럼 문자열을 구성하고 있는 문자만으로 구성된 것도 아니거와, 일정하게 1개의 크기로 구성되어 있지도 않다. 따라서 우리는 각 단계의 문자열 결합형태가 먼저 strs 원소와 일치하는지를 판단해야 한다.

단순히 현재 문자열 결합형태가 현재 배열의 단어조각과 일치하는지 검사하는 것은 매우 간단하다. 하지만 일치여부를 통해서는 제대로 된 최솟값을 계산할 수 없다. 만약 banana라는 문자열이 있고, 단어조각 중에 banana가 존재한다면 일치여부를 통해 서로 동일함을 판단할 수 있고, 이 경우에는 당연히 그 자체가 문자열이기 때문에 최솟값은 1로 판단할 수 있다. 그렇지만, 문제 조건에 의해 단어조각의 크기는 항상 1 <= n <= 5 범위에 있기 때문에 이를 벗어나는 문자열은 해당 방식으로는 답을 찾아낼 수 없다. 또한 각 단계에 일치하는 단어 조각들이 있다고 해서 항상 최종 단계의 문자열을 만들 수 있는 것은 아니다. 예를 들어 ban 조각이 있음을 확인했고 banan 조각이 있음을 확인했지만, 이 둘을 가지고는 banana 문자열을 만들 수 없다. 따라서 단순히 현재 결합형태 단계와 단어조각의 일치여부를 검사하는 것으로는 최솟값을 구할 수 없다.

그렇다면 어떤 방식으로 현재 단계의 문자열 결합형태와 단어조각의 상관관계를 정립할 수 있을까? 일단 모든 문자열은 첫 번째 결합형태 단계에서는 문자열의 첫 글자 하나로 시작함을 알 수 있다. banana의 경우를 예로 들자면 b로 시작하는 것과 같다. 그리고 그 뒤에 위치한 문자를 하나씩 뒤에 붙여가며 최종적으로 문자열을 완성시킨다.

문자열이 앞에서부터 뒤로 진행되며 완성되어가기 때문에, 우리는 현재 단계의 문자열 결합형태가 지금의 단어조각으로 끝날 수 있는지 아닌지를 판단해볼 수 있다. 예를 들어 현재 문자열 결합형태가 ban 이라면 단어조각 중에 n, an 또는 ban이 있는지 검사할 수 있다. 이처럼 뒤에서부터 검색하는 이유는 다음 단계의 결합형태는 현재 문자열 결합형태 마지막에 새로 한 문자가 추가되기 때문이다. 또한 새로 만들어진 문자열과 일치하는 단어조각이 있는지도 검사할 수 있다. 무엇보다 가장 핵심이 되는 부분은 이전에 구한 단어조각과 다른 새로운 단어조각을 찾을 수 있으며, 이를 통해 최솟값이 갱신될 수 있는지 체크해볼 수 있다. 관련해서 자세한 이야기는 DP 알고리즘을 적용하는 부분에서 더 세세하게 살펴볼 것이다.

따라서 우리는 현재 단계의 문자열 결합형태가 각 단어조각으로 끝나는지를 판단해서 다음 작업을 수행할 것이다. 자바스크립트에서는 이와 관련된 문자열 메서드를 제공한다. 따라서 다음의 코드를 통해 이 같은 작업을 손쉽게 할 수 있다.

// current : 현재 단계의 문자열 결합형태
// endswith : str로 current가 끝나는 경우 true, 아니면 false
for(const str of strs) {
  if (current.endsWith(str)) { ... }
}

3) DP 알고리즘과의 상관관계

자 그렇다면 이제 DP 알고리즘을 적용하기 위해 다시 반복되는 패턴을 분석해보자. 실제 주어진 데이터를 가지고 예시를 들어볼 것이다. 지금 strs로 주어진 데이터는 ['ba', 'na', 'n', 'a']이고 완성해야할 문자열은 "banana"이다. 따라서 위의 경우와 마찬가지로 다음 6가지의 current (문자열 결합형태)가 존재할 것이다. 그리고 각 단계에서 endsWith 메서드로 찾아낸 단어조각은 다음과 같을 것이다.

b : 해당하는 단어조각 없음
ba : ba 와 a
ban : n
bana : na 와 a
banan : n
banana : na 와 a

1번에서는 해당하는 단어조각이 없기 때문에 당연히 카운트할 수 없다.

2번은 두 개의 단어조각을 찾았는데, 이 중에서 a 단어조각을 사용해서는 ba를 완성시킬 수 없다. 왜냐하면 a를 사용하고 남은 문자열은 b가 되는데, 이는 1번에서 이미 만들 수 없는 문자열로 판단되었기 때문이다. 따라서 ba 단어조각을 사용해 해당 단계의 결합형태를 만들 수 있고, 이때 사용횟수는 1회가 된다.

3번은 n 단어조각만 존재하고, ban을 만들기 위해서는 2번 과정에서 n을 추가하기만 하면 된다. 따라서 ban을 만들기 위해 사용한 단어 조각의 개수는 2회가 된다.

4번은 na와 a 두 개의 단어조각이 있다. 두 개의 단어조각 모두 현재 단계의 결합형태 bana를 만들 수 있다. na 단어조각의 경우는 2번과 조합해서 만들 수 있으며, a 단어조각의 경우는 3번과 조합해서 만들 수 있다. 각각의 단어조각 사용횟수는 na가 2회 (2번을 만들기 위한 사용횟수 + 현재 단어조각), a의 경우는 3회 (3번을 만들기 위한 사용횟수 + 현재 단어조각)이 된다. 당연히 최솟값을 골라야하기 때문에 4번의 조각 사용횟수는 2회가 될 것이다.

5번은 n 단어조각만 사용할 수 있다. 해당 조각을 이용해서 banan을 만들기 위해서는 4번에서 현재 단어 조각을 추가하는 것이다. 4번의 사용횟수가 2회였기 때문에 이 경우 사용횟수는 총 3회가 될 것이다.

6번은 4번과 동일하다. 두 개 단어조각 모두 사용할 수 있으나 na 조각을 사용하는 경우는 "bana"를 만들기 위해 사용한 횟수 + 1이 될 것이고 a 조각을 사용하는 경우엔 "banan"을 만들기 위해 사용한 횟수 + 1이 될 것이다. 따라서 6번 결합형태이자 최종 문자열을 만들기 위해 사용한 최솟값은 3이 됨을 알 수 있다.

우리는 위 과정을 통해 이를 DP 알고리즘으로 곧바로 적용할 수 있음을 알 수 있다. 각 단계는 이전 단계에서 사용한 횟수를 얻어와서 현재 단어조각의 사용 횟수인 1을 더해주는 것을 볼 수 있다. 이때 이전 단계가 되는 지점은 현재 단어조각의 길이를 뺀 지점이 된다. 예를 들어 6번의 경우를 보면 현재 단계의 문자열은 banana로 총 6의 길이를 가지고 있다. 이때 na를 한 번 사용하기 위해 필요한 문자열은 bana가 되어야 함이 자명하다. 이는 4번의 경우이기 때문에 4번에서의 최소값에서 1을 더해주어 현재 6단계에서의 값을 구할 수 있다. 따라서 DP 배열과 점화식을 다음과 같이 정의할 수 있다.

DP[i] : i번째 단계에서 사용한 단어조각의 최솟값
DP[i] = Math.min(DP[i], DP[현재 문자열 길이 - 단어조각 길이] + 1)

이를 통해 DP 알고리즘을 직접 구현해보자.

4) DP 알고리즘 구현

먼저 탐색의 기반이 되는 DP 배열을 정의해주자. 문자열의 크기만큼 반복하기 때문에 DP 배열 역시 문자열과 동일한 크기를 가지면 된다. 이때 초기값으로는 Infinity를 넣어주자. 최솟값을 찾아 갱신해야 하기 때문에 가장 큰 값으로 넣어주는 것이며, 또한 문제 조건에 의해 문자열을 만들 수 없는 경우도 존재하기 때문에 만약 이 값이 Infinity인 경우엔 주어진 단어조각으로 해당 문자열을 만들 수 없음을 판단할 수 있다.

// dp 배열 선언
const n = t.length;
const dp = new Array(n).fill(Infinity);

그리고 앞서 살펴본 과정을 모두 적용하면 된다. 각 단계의 문자열 결합형태를 만들기 위해서는 가장 외부의 반복문이 문자열 크기만큼 순회할 것이다. 그리고 문자를 하나씩 뒤로 붙여가며 각 단계를 형성하게 된다.

for(let i = 0; i < n; i++) {
  // current 는 각 단계의 문자열 결합형태
  const current = t.substr(0, i+1);
  
  for(const str of strs) {
    if (current.endsWith(str)) {
      // 현재 단계의 문자열과 단어조각 간 길이차를 구해주자
      const diff = current.length - str.length;
      
      // 둘의 차가 0이라는 것은 서로 완벽히 일치함을 의미
      // 즉 해당 조각을 1번 사용하는 것으로 지금 문자열 완성 가능
      if (diff === 0) {
        dp[i] = 1;
      } 
      // 그렇지 않은 경우엔 점화식을 적용
      else {
        // index이기 때문에 1을 뺀 값으로 접근해야 함
        dp[i] = Math.min(dp[i], dp[diff-1] + 1);
      }
    }
  }
}

그리고 정답은 dp 배열의 가장 마지막에 들어있을 것이다. 이때 해당 원소의 값이 여전히 Infinity라면 문자열을 만들 수 없었다는 것을 의미하므로 -1을 리턴해주도록 하자.

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

5) 전체코드

문자열을 처음부터 하나씩 늘려가며 접근함과 동시에, 각 단계의 문자열을 뒤에서 부터 접근하여 단어조각의 사용여부를 판단하는 점을 파악할 수 있다면 적용하는 DP 알고리즘 자체는 대단히 어렵지 않기 때문에 비교적 용이하게 풀이가 가능할 것으로 생각된다. 접근 방식을 떠올리는 사고력이 다소 필요한 문제였던 것 같다. 주석을 제외한 전체코드는 다음과 같다.

function solution (strs, t) {
  const n = t.length;
  const dp = new Array(n).fill(Infinity);
  
  for(let i = 0; i < n; i++) {
    const current = t.substr(0, i+1);
    
    for(const str of strs) {
      if (current.endsWith(str)) {
        const diff = current.length - str.length;
        
        if (!diff) {
          dp[i] = 1;
        } else {
          dp[i] = Math.min(dp[i], dp[diff-1] + 1);
        }
      }
    }
  }
  return dp[n-1] === Infinity ? -1 : dp[n-1];
}