파이썬으로 문자열 리스트에서 연결된 단어 개수 계산하는 방법

문자열로 이루어진 리스트가 있다고 가정해 보겠습니다. 이때 찾아야 할 것은 리스트 안에 있는 다른 단어들을 연결(concatenate)하여 만들어진 단어의 개수입니다. 연결 과정에서 이미 사용한 단어를 다시 재사용할 수 있으며, 원하는 만큼 몇 번이고 연결해도 괜찮습니다.

예를 들어 입력이 다음과 같다면,

words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"]

출력은 2가 됩니다. 그 이유는 다음과 같습니다.

"helloworld"는 "hello"와 "world"를 연결한 단어입니다.
"worldfamous"는 "world"와 "famous"를 연결한 단어입니다.

해결 접근 방법

이 문제는 트라이(Trie) 자료구조와 깊이 우선 탐색(DFS)을 조합하면 효율적으로 해결할 수 있습니다. 전체적인 흐름은 다음과 같습니다.

새로운 맵(딕셔너리)으로 트라이(trie)를 생성하고, 모든 단어를 트라이에 삽입합니다.
각 단어를 순회하며 문자 하나씩 레이어(layer)를 따라 내려가고, 단어가 끝나는 지점에 "*" 마커를 저장합니다.
dfs() 함수를 정의합니다. 이 함수는 word(검사할 단어)와 num_concatenated_words(지금까지 연결된 단어 수)를 인자로 받습니다.
dfs() 내부에서 각 인덱스 i와 문자 w를 순회하면서 다음을 수행합니다.
- 현재 레이어에 "*" 마커가 있으면, 남은 부분(word[i:])에 대해 연결 단어 수를 1 증가시켜 재귀적으로 dfs()를 호출하고, 결과가 True면 True를 반환합니다.
- 현재 문자 w가 레이어에 없으면 False를 반환합니다.
- 레이어를 layer[w]로 이동합니다.
단어 끝까지 도달했을 때 "*" 마커가 존재하고 연결된 단어 수가 1 이상이면 True를, 아니면 False를 반환합니다.
메인 로직에서는 count를 0으로 초기화한 뒤, 모든 단어에 대해 dfs(word, 0)의 결과를 더하고 최종 count를 반환합니다.

구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

class Solution:
   def solve(self, words):
      trie = {}
      for word in words:
         layer = trie
         for w in word:
            if w not in layer:
               layer[w] = {}
            layer = layer[w]
         layer["*"] = ()

      def dfs(word, num_concatenated_words):
         layer = trie

         for i, w in enumerate(word):
            if "*" in layer:
               if dfs(word[i:], num_concatenated_words + 1):
                  return True
            if w not in layer:
               return False
            layer = layer[w]

         if "*" in layer and num_concatenated_words >= 1:
            return True
         return False

      count = 0
      for word in words:
         count += dfs(word, 0)
      return count

ob = Solution()
words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"]
print(ob.solve(words))

입력

["hello", "world", "helloworld", "famous", "worldfamous", "programming"]