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

[79] 단어 퍼즐

책 구매하기

문제 정보

• 분류: 동적 계획법
• 정답률: 21%
• 권장 시간 복잡도: O(N * L)
• 핵심 키워드: 문자열 DP, 사전, 길이 집합, 최소 인덱스
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12983

문제를 읽을 때 체크할 포인트

문자열을 앞에서부터 만들 수 있는지 DP로 체크하면 된다. dp[i]를 '앞에서 i글자까지 만들 수 있는가'로 두고, 가능한 단어 길이만큼 뒤를 검사하면 된다.

여기서는 정답 자체보다 '상태를 어떻게 잡을 것인가'가 먼저다. 현재 상태에서 다음 상태로 가는 비용만 잘 세우면, 긴 설명보다 점화식 하나가 더 강하다.

풀이 흐름

1. strs를 집합으로 만들어 빠르게 검사한다.
2. dp[0]=True로 시작한다.
3. 만들 수 있는 위치 i에서 단어 길이별로 substr을 확인해 dp를 전파한다.

구현할 때 놓치기 쉬운 부분

앞에서부터 그때그때 맞는 조각을 greedy하게 붙이면 중간에 막히기 쉽다. 특정 위치까지 문자열을 만들 수 있는지 DP로 쌓아 가는 편이 안정적이다.

파이썬 정답 코드

def solution(strs, t):
  # strs를 집합으로 만들어 빠르게 검사한다.
  word_set = set(strs)
  lengths = sorted({len(word) for word in strs})
  n = len(t)
  INF = 10 ** 9
  dp = [INF] * (n + 1)
  dp[0] = 0

  # dp[0]=True로 시작한다.
  for i in range(n):
    # 만들 수 있는 위치 i에서 단어 길이별로 substr을 확인해 dp를 전파한다.
    if dp[i] == INF:
      continue
    for length in lengths:
      ni = i + length
      if ni > n:
        break
      if t[i:ni] in word_set:
        dp[ni] = min(dp[ni], dp[i] + 1)

  return dp[n] if dp[n] != INF else -1

시간 복잡도

N은 t의 길이, L은 strs에 들어 있는 서로 다른 단어 길이 개수이다.

목표 문자열의 각 위치를 시작점으로 보면서 붙일 수 있는 단어 길이를 확인한다. 서로 다른 길이 종류 수를 L로 두면 위치 N개마다 길이 후보 L개를 검사하는 구조이다.

따라서 시간 복잡도는 O(N * L)이다.