Funcia
Lv.3dphashstring

단어로 쪼개기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

띄어쓰기가 빠진 문자열 s와 단어 사전 words가 주어집니다.

s를 앞에서부터 잘라 모든 조각이 사전에 있는 단어가 되도록 나눌 수 있는지 판단해 true 또는 false를 반환하세요. 사전의 단어는 몇 번이든 다시 쓸 수 있습니다.

입출력 예

swordsresult
"applepenapple"["apple", "pen"]true
"catsandog"["cats", "dog", "sand", "and", "cat"]false
"aaaaaaa"["aaa", "aaaa"]true

입출력 예 설명

예 1 — "apple" + "pen" + "apple"로 나뉩니다. "apple"을 두 번 썼습니다.

예 2 — "cats" + "and"나 "cat" + "sand"까지는 가능하지만 남는 "og"가 사전에 없습니다.

예 3 — "aaa" + "aaaa"(또는 "aaaa" + "aaa")로 나뉩니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(s: string, words: string[]) → bool

제한 사항

  • 1≤1 \le s.length ≤100,000\le 100{,}000
  • 1≤1 \le words.length ≤1,000\le 1{,}000
  • 1≤1 \le words[i].length ≤20\le 20
  • s와 words[i]는 영어 소문자로만 이루어져 있습니다. 사전에 같은 단어가 여러 번 있을 수 있습니다.

기대 복잡도

시간
O(N * L)
공간
O(N + total word length)

입출력 예

swords기대 출력
"applepenapple"["apple","pen"]true
"catsandog"["cats","dog","sand","and","cat"]false
"aaaaaaa"["aaa","aaaa"]true

힌트

힌트

ok[i] = "s의 앞 i글자를 단어들로 나눌 수 있는가"로 정의하는 DP입니다. ok[0] = true입니다.

ok[i]가 참이려면, 어떤 단어 w에 대해 ok[i - |w|]가 참이고 s[i - |w| .. i)가 w와 같아야 합니다.

핵심은 단어 길이가 20 이하라는 점입니다. 각 i에서 직전 위치 전부를 볼 필요 없이, 길이 1~20인 조각만 해시 집합에서 찾으면 됩니다.

  • 해시 집합: i마다 길이 L = 1..20인 조각을 잘라 집합에 있는지 확인 → O(N⋅20)O(N \cdot 20)번 조회
  • 트라이: ok[i]가 참인 위치에서 트라이를 따라 앞으로 최대 20글자 걸어가며, 단어 끝에 닿는 위치를 참으로 표시

복잡도 목표

각 i에서 이전의 모든 위치 j를 보며 s[j..i)를 잘라 확인하면 O(N2)O(N^2)개의 조각을 만들게 되어 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4010판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.