내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
단어 퍼즐
ps:problems:programmers:12983
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 단어 퍼즐 ====== ===== 풀이 ===== * n = 문자열 t의 길이, m = 배열 strs의 크기, k = 단어 조각의 길이 * dp[i] 를 t[:i+1]을 만들기 위해 사용하는 최소의 단어 수라고 하면, 간단히 점화식이 세워진다. * dp[i] = min_k(dp[i-k] + 1), where t[i-k:i+1]∈strs * 문제 조건에서는 1≤k≤5 이므로 dp테이블을 크기가 t인 리스트로 만드는 대신에, 크기가 5인 리스트만 유지하면서 슬라이딩 윈도우 방식으로 계산하는 것도 가능하다. 그러나 실제로 그렇게 구현은 하지 않았다. * 저 점화식을 계산하려면 i에 대한 루프를 한번 돌 때마다, k개의 문자열에 대해서 문자열이 strs 안에 포함되는지를 체크해야 한다. 포함여부를 O(1)에 체크하기 위해서, 미리 O(m)시간에 strs를 set으로 변환하는 전처리가 필요하다. * 이렇게 전처리를 한다면, k≤5를 그냥 상수 취급할 때, 시간 복잡도는 O(m+n)이다 * 만약, k를 상수취급하지 않고, 복잡도 계산에 포함시킨다면, set을 만드는 데에는 O(mk)이 들고, k길이의 문자열 k개를 set에서 포함여부를 확인하는 것은 O(k^2), 그래서 총 O(mk + nk^2)이 걸린다. 이것을 효율적으로 하기 위해서는, [[[ps:라빈-카프 알고리즘|Rabin fingerprint]]와 같은 rolling hash를 이용해서, k길이 문자열에 대한 해시를 O(1)에 계산해줄 수 있다. 그러면 문자열 한개의 set비교 코스트가 O(k)에서 O(1)로 줄게 되므로, k개의 문자열에 대한 비교를 총 n번 하는 시간은 O(nk). 그래서 총 시간을 O(mk + nk)로 단축시킬 수 있다. * 물론 이 문제에서는 k가 5밖에 안되므로, 이렇게 구현한 [[#코드 2 - Rabin fingerprint|코드 2]]가 그냥 구현한 [[#코드 1 - 일반적 스트링 매칭|코드 1]] 보다 더 느렸다.. ===== 코드 ===== ==== 코드 1 - 일반적 스트링 매칭 ==== <dkpr py> """Solution code for "Programmers 12983. 단어 퍼즐". - Problem link: https://programmers.co.kr/learn/courses/30/lessons/12983 - Solution link: http://www.teferi.net/ps/problems/programmers/12983 """ INF = float('inf') def solution(strs, t): strs_set = set(strs) dp = [0] * (len(t) + 1) for i in range(1, len(t) + 1): dp[i] = min((dp[prev] + 1 for prev in range(max(0, i - 5), i) if t[prev:i] in strs_set), default=INF) return dp[-1] if dp[-1] != INF else -1 </dkpr> ==== 코드 2 - Rabin fingerprint ==== <dkpr py> """Solution code for "Programmers 12983. 단어 퍼즐". Using Rabin-fingerprint for string matching. - Problem link: https://programmers.co.kr/learn/courses/30/lessons/12983 - Solution link: http://www.teferi.net/ps/problems/programmers/12983 """ from teflib import string INF = float('inf') def solution(strs, t): p_hashes = set(string.fingerprint(s) for s in strs) t_hashes = [list(string.gen_fingerprints(t, l)) for l in range(1, 6)] dp = [0] * (len(t) + 1) for i in range(1, len(t) + 1): dp[i] = min((dp[i - x] + 1 for x in range(1, min(5, i) + 1) if t_hashes[x - 1][i - x] in p_hashes), default=INF) return dp[-1] if dp[-1] != INF else -1 </dkpr> * Dependency: [[:ps:teflib:string#fingerprint|teflib.string.fingerprint]], [[:ps:teflib:string#gen_fingerprint|teflib.string.gen_fingerprint]] {{tag>프로그래머스 ps:problems:programmers:Level_4 ps:teflib:fingerprint ps:teflib:gen_fingerprint}}
ps/problems/programmers/12983.txt
· 마지막으로 수정됨: 2021/01/21 15:24 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로