๋จ์ด ํผ์ฆ
๋ฌธ์ ์ค๋ช
๋จ์ด ํผ์ฆ์ ์ฃผ์ด์ง ๋จ์ด ์กฐ๊ฐ๋ค์ ์ด์ฉํด์ ์ฃผ์ด์ง ๋ฌธ์ฅ์ ์์ฑํ๋ ํผ์ฆ์ ๋๋ค. ์ด๋, ์ฃผ์ด์ง ๊ฐ ๋จ์ด ์กฐ๊ฐ๋ค์ ๊ฐ๊ฐ ๋ฌดํ๊ฐ์ฉ ์๋ค๊ณ ๊ฐ์ ํฉ๋๋ค. ์๋ฅผ ๋ค์ด ์ฃผ์ด์ง ๋จ์ด ์กฐ๊ฐ์ด [“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 |
์ ์ถ๋ ฅ ์ ์ค๋ช
๋ฌธ์ ์ ์์์ ๊ฐ์ต๋๋ค.
์
์ถ๋ ฅ ์ #2
"ap" 1๊ฐ, "ple" 1๊ฐ์ ์ด 2๊ฐ๋ก "apple"์ ๋ง๋ค ์ ์์ผ๋ฏ๋ก ํ์ํ ๋จ์ด ๊ฐ์์ ์ต์๊ฐ์ 2๋ฅผ return ํฉ๋๋ค.
์
์ถ๋ ฅ ์ #3
์ฃผ์ด์ง ๋จ์ด๋ก๋ "banana"๋ฅผ ๋ง๋ค ์ ์์ผ๋ฏ๋ก -1์ return ํฉ๋๋ค.
๋์ ํธใน์ด
- ์ฃผ์ด์ง ๋จ์ด๋ค๋ก ๋ฌธ์๋ฅผ ๋ง๋๋ ๋ฌธ์ .
- ๋จ์ด๋ฅผ ๋์ ๋๋ฆฌ๋ก ๋ง๋ค์ด์, ๋ฌธ์์ด์์ ๋จ์ด๋ค์ ํ๋์ฉ ์ง์ฐ๋ ๋ฐฉ์์ผ๋ก ์ฌ๊ทํธ์ถ์ ์ผ๋๋ฐ ์๋ฌ๋๋ค.
- ํ ์คํธ ์ผ์ด์ค๋ ๋ค ํต๊ณผํ์ง๋ง...
- 1์ฐจ ์๋ ์์ค์ฝ๋
def solution(strs, t):
answer = 0
method_count = []
dict = {}
strs.sort(key=lambda x:x) #์ํ๋ฒณ์ ์ฌ์ ๊ตฌ์ฑ
for s in strs:
if s[0] in dict:
dict[s[0]].append(s)
else:
dict[s[0]] = [(s)]
#print(dict)
def deletedict(tt,c):
dct = dict[tt[0]]
for dd in dct:
#print(tt, "-", dd, end=" -> ")
if len(dd) > len(tt):
#print("์คํจ")
return
elif dd == tt:
#print("๋์ผ", c, "์ ์ฅ")
method_count.append(c)
return
else:
#print("๊ณ์")
for pair in zip(tt, dd):
if pair[0] != pair[1]:
return
ttt = tt[len(dd):]
#print(ttt)
deletedict(ttt,c+1)
deletedict(t,0)
if len(method_count) > 0:
return min(method_count) + 1
return -1
- ๋ฐํ์์๋ฌ?
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.27ms, 10.2MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 4 ใ ํต๊ณผ (1.01ms, 10.3MB)
ํ
์คํธ 5 ใ ํต๊ณผ (135.23ms, 10.5MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 7 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
ํ
์คํธ 8 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 9 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 10 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 11 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 12 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.35ms, 10.3MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.22ms, 10.3MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.06ms, 10.2MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.03ms, 10.3MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.03ms, 10.2MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 2 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 3 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 4 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 5 ใ ํต๊ณผ (0.06ms, 10.2MB)
- ์๋ฌด๋๋... ์ฌ๊ทํธ์ถ์ด ๋๋ฌด ๋ง์์๊ฒ ์ง?
- ํ์ด์ฌ์ ์ฌ๊ท ํธ์ถ์ ์ต๋ 1000๋ฒ๊น์ง๋ง ํ๋ฝํ๋ค.
- ์ด ํ๊ณ ๋ํํ๋ ค๋ฉด... ์๋ ๋ช ๋ น์ ์ฌ์ฉํ๋ค.
import sys
limit_number = 15000
sys.setrecursionlimit(limit_number)
- ๊ทธ๋๋ ์๋ฌ๋๋ค. ์ฌ๊ทํธ์ถ๋ก ํ๋ฉด ์๋๋ ๋ฌธ์ ์ธ๊ฐ๋ณด๋ค.
- ์๋ผ๋ธ ๋จ์ด๋ฅผ list(set()) ํ๋ฒ์ฉ ํด์ ์ค์ด๋ ๋ฐฉ์์ด ์๊ธด ํ์ง... ๊ทธ๋ ๊ฒ ํด์ผ๋๋? ๊ทธ๋ผ BFS์ธ๊ฐ...
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.27ms, 10.3MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.97ms, 10.1MB)
ํ
์คํธ 5 ใ ํต๊ณผ (133.64ms, 10.4MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 7 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
ํ
์คํธ 8 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
ํ
์คํธ 9 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
ํ
์คํธ 10 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
ํ
์คํธ 11 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
ํ
์คํธ 12 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.35ms, 10.3MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.24ms, 10.2MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.06ms, 10.2MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.02ms, 10.3MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 2 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 3 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 4 ใ ์คํจ (๋ฐํ์ ์๋ฌ)
ํ
์คํธ 5 ใ ํต๊ณผ (0.07ms, 10.2MB)
- ์๋ฒ์ ๋น ๋ฅธ๋ฐ ๋ค ์คํจ ใ ใ ใ
def solution(strs, t):
answer = 1
dp = [0]
dict = {}
#strs.sort(key=lambda x:x) #์ํ๋ฒณ์ ์ฌ์ ๊ตฌ์ฑ
for s in strs:
if s[0] in dict:
dict[s[0]].append(s)
else:
dict[s[0]] = [(s)]
while 0 < len(dp):
_tmp = []
for index in dp:
tt = t[index:]
dct = dict[tt[0]]
for dd in dct:
print(answer,":",tt, "-", dd, end=" --> ")
if len(dd) > len(tt):
print("์คํจ")
continue
elif dd == tt:
print("์ ๋ต")
return answer
break
else:
print("๊ณ์")
for pair in zip(tt, dd):
if pair[0] != pair[1]:
continue
_tmp.append(index + len(dd))
answer += 1
dp = list(set(_tmp))
return -1
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 2 ใ ์คํจ (0.03ms, 10.1MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.04ms, 10MB)
ํ
์คํธ 5 ใ ์คํจ (0.03ms, 10.2MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.01ms, 10.4MB)
ํ
์คํธ 7 ใ ์คํจ (0.03ms, 10.2MB)
ํ
์คํธ 8 ใ ์คํจ (0.06ms, 10.3MB)
ํ
์คํธ 9 ใ ์คํจ (0.07ms, 10.2MB)
ํ
์คํธ 10 ใ ์คํจ (0.07ms, 10.1MB)
ํ
์คํธ 11 ใ ์คํจ (0.08ms, 10.2MB)
ํ
์คํธ 12 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.04ms, 10.2MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.06ms, 10.2MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.03ms, 10.1MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 17 ใ ์คํจ (0.01ms, 10.2MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.03ms, 10.2MB)
ํ
์คํธ 19 ใ ์คํจ (0.02ms, 10.2MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ์คํจ (0.44ms, 10.1MB)
ํ
์คํธ 2 ใ ์คํจ (0.42ms, 10.3MB)
ํ
์คํธ 3 ใ ์คํจ (0.29ms, 10.3MB)
ํ
์คํธ 4 ใ ์คํจ (0.67ms, 10.3MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.34ms, 10.2MB)
- ์ฌ๊ธฐ์ผ์ ํ์ผ๋...
- dict๊ฐ ํ์ด์ฌ ์์ฝ์ด๋ผ์ ๋ฐ๊ฟ
def solution(strs, t):
answer = 1
len_t = len(t)
visited = {(0, "")}
queue = [(0, "")]
string_dict = {}
for s in strs:
if s[0] in string_dict:
string_dict[s[0]].append(s)
else:
string_dict[s[0]] = [s]
while queue:
temp = set()
for index, str in queue:
dct = string_dict.get(t[index], [])
for dd in dct:
len_dd = len(dd)
len_tt = len_t - index
if len_dd <= len_tt:
mismatch = False
for i in range(len_dd):
if t[index+i] != dd[i]:
mismatch = True
break
if mismatch:
continue
if len_dd == len_tt:
return answer
new_index = index + len_dd
if new_index > len_t:
continue
if (new_index, dd) not in visited:
visited.add((new_index, dd))
temp.add((new_index, dd))
answer += 1
queue = list(temp)
return -1
- ํจ์จ์ฑ ํ ์คํธ์์ ์๊ฐ์ด๊ณผ ๋์จ๋ค.
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.08ms, 10.3MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.07ms, 10.1MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.13ms, 10.1MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.01ms, 10.4MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.37ms, 10.1MB)
ํ
์คํธ 8 ใ ํต๊ณผ (4.28ms, 10.3MB)
ํ
์คํธ 9 ใ ํต๊ณผ (5.67ms, 10.3MB)
ํ
์คํธ 10 ใ ํต๊ณผ (6.55ms, 10.3MB)
ํ
์คํธ 11 ใ ํต๊ณผ (8.14ms, 10.3MB)
ํ
์คํธ 12 ใ ํต๊ณผ (0.01ms, 10MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.03ms, 10.1MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.05ms, 10.2MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.03ms, 10.1MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
ํ
์คํธ 2 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
ํ
์คํธ 3 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
ํ
์คํธ 4 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
ํ
์คํธ 5 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
- ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ผ๋ก ๊ณ ์ณค๋๋ฐ ์๊ฐ ์ด๊ณผ
def solution(strs, t):
len_t = len(t)
dp = [-1] * (len_t + 1)
dp[0] = 0
string_dict = {}
for s in strs:
if s[0] in string_dict:
string_dict[s[0]].append(s)
else:
string_dict[s[0]] = [s]
for i in range(len_t):
if dp[i] == -1:
continue
for dd in string_dict.get(t[i], []):
len_dd = len(dd)
len_tt = len_t - i
if len_dd > len_tt:
continue
mismatch = False
for j in range(len_dd):
if t[i + j] != dd[j]:
mismatch = True
break
if mismatch:
continue
if dp[i + len_dd] == -1 or dp[i + len_dd] > dp[i] + 1:
dp[i + len_dd] = dp[i] + 1
return dp[len_t]
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.04ms, 10.2MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.01ms, 10.4MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.03ms, 10.1MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.13ms, 10.2MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.01ms, 10.4MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.15ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (2.27ms, 10.3MB)
ํ
์คํธ 9 ใ ํต๊ณผ (2.40ms, 10.4MB)
ํ
์คํธ 10 ใ ํต๊ณผ (2.72ms, 10.2MB)
ํ
์คํธ 11 ใ ํต๊ณผ (3.33ms, 10.3MB)
ํ
์คํธ 12 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.03ms, 10.2MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.03ms, 10.2MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.02ms, 10.4MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (206.62ms, 10.7MB)
ํ
์คํธ 2 ใ ํต๊ณผ (203.37ms, 10.7MB)
ํ
์คํธ 3 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
ํ
์คํธ 4 ใ ํต๊ณผ (211.06ms, 10.8MB)
ํ
์คํธ 5 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
- for๋ฌธ ํ๋ ๊ณ ์ณค๋ค๊ณ ๋นจ๋ผ์ง๋๊ฑฐ ์ข ์ด์ํ๋ค. ใ ก.ใ ก ์ด๋นจ์ธ๊ฐ?
def solution(strs, t):
len_t = len(t)
dp = [-1] * (len_t + 1)
dp[0] = 0
string_dict = {}
for s in strs:
if s[0] in string_dict:
string_dict[s[0]].append(s)
else:
string_dict[s[0]] = [s]
for i in range(len_t):
if dp[i] == -1:
continue
for dd in string_dict.get(t[i], []):
len_dd = len(dd)
len_tt = len_t - i
if len_dd > len_tt:
continue
j = 0
while j < len_dd and t[i + j] == dd[j]:
j += 1
if j < len_dd:
continue
if dp[i + len_dd] == -1 or dp[i + len_dd] > dp[i] + 1:
dp[i + len_dd] = dp[i] + 1
return dp[len_t]
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.04ms, 10.2MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.03ms, 10.3MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.06ms, 10.2MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.12ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (1.61ms, 10.3MB)
ํ
์คํธ 9 ใ ํต๊ณผ (1.82ms, 10.1MB)
ํ
์คํธ 10 ใ ํต๊ณผ (2.07ms, 10.2MB)
ํ
์คํธ 11 ใ ํต๊ณผ (2.36ms, 10.1MB)
ํ
์คํธ 12 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.04ms, 10.2MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (171.62ms, 10.7MB)
ํ
์คํธ 2 ใ ํต๊ณผ (174.13ms, 10.9MB)
ํ
์คํธ 3 ใ ํต๊ณผ (166.47ms, 10.5MB)
ํ
์คํธ 4 ใ ํต๊ณผ (157.20ms, 10.8MB)
ํ
์คํธ 5 ใ ํต๊ณผ (114.42ms, 10.5MB)
๊ณ ์์ ํ์ด. ใฑใ ๋น ๋ฆ
def solution(strs, t):
n = len(t)
memo = [float("inf")] * (n + 1)
memo[0] = 0
sizes = set(len(s) for s in strs)
strs = set(strs)
for i in range(n + 1):
for size in sizes:
if i + size < n + 1 and t[i:i + size] in strs:
memo[i + size] = min(memo[i + size], memo[i] + 1)
return memo[n] if memo[n] < float("inf") else -1
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.04ms, 10.3MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.05ms, 10.3MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.06ms, 10.1MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.12ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (1.00ms, 10.2MB)
ํ
์คํธ 9 ใ ํต๊ณผ (1.05ms, 10.1MB)
ํ
์คํธ 10 ใ ํต๊ณผ (1.13ms, 10.3MB)
ํ
์คํธ 11 ใ ํต๊ณผ (1.13ms, 10.3MB)
ํ
์คํธ 12 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.02ms, 10.3MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.01ms, 10.3MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.02ms, 10.3MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (29.72ms, 10.7MB)
ํ
์คํธ 2 ใ ํต๊ณผ (26.69ms, 10.8MB)
ํ
์คํธ 3 ใ ํต๊ณผ (24.50ms, 10.8MB)
ํ
์คํธ 4 ใ ํต๊ณผ (31.82ms, 10.8MB)
ํ
์คํธ 5 ใ ํต๊ณผ (31.75ms, 10.6MB)
- enumerate ์ฌ์ฉ
def solution(strs, t):
counts = [20001] * len(t)
for i, c in enumerate(t):
for s in strs:
if s[-1] == c and t[i - len(s) + 1: i + 1] == s:
if i - len(s) == -1: #์์์ง์
counts[i] = 1
else:
#nd = counts[i - len(s)] + 1
#pd = counts[i]
counts[i] = min(counts[i - len(s)] + 1, counts[i])
return counts[-1] if counts[-1] < 20001 else -1
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.04ms, 10.3MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.00ms, 10.1MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.06ms, 10.1MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.12ms, 10.1MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.18ms, 10.1MB)
ํ
์คํธ 8 ใ ํต๊ณผ (1.97ms, 10.1MB)
ํ
์คํธ 9 ใ ํต๊ณผ (2.26ms, 10.3MB)
ํ
์คํธ 10 ใ ํต๊ณผ (2.50ms, 10.1MB)
ํ
์คํธ 11 ใ ํต๊ณผ (2.81ms, 10.3MB)
ํ
์คํธ 12 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.02ms, 10MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.03ms, 10.3MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.02ms, 10.3MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (196.39ms, 10.7MB)
ํ
์คํธ 2 ใ ํต๊ณผ (196.14ms, 10.7MB)
ํ
์คํธ 3 ใ ํต๊ณผ (194.25ms, 10.8MB)
ํ
์คํธ 4 ใ ํต๊ณผ (202.01ms, 10.7MB)
ํ
์คํธ 5 ใ ์คํจ (์๊ฐ ์ด๊ณผ)
- ๋๋ ์์ง ๋ฉ์๊ตฌ๋... ใ ก.ใ ก;
def solution(strs, t) :
dp = {i: float('inf') for i in range(len(t))}
for j in range(len(t)-1, -1, -1):
for k in range(1,6):
# print("------------------------------------------------------------------")
# print("j: ", j, " k: ", k, " t[j:j+k]", t[j:j+k])
if j+k > len(t) :
break
if t[j:j+k] in strs:
# print("==============================================================")
# print("dp.get(j): ", dp.get(j), " dp.get(j+k, 0)+1: ", dp.get(j+k, 0)+1)
dp[j] = min(dp.get(j), dp.get(j+k, 0)+1)
# print("dp: ", dp)
if dp[0] == float('inf') :
return -1
else :
return dp[0]
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.06ms, 10.1MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.01ms, 10MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.11ms, 10.1MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.11ms, 10.2MB)
ํ
์คํธ 6 ใ ํต๊ณผ (0.02ms, 10.2MB)
ํ
์คํธ 7 ใ ํต๊ณผ (0.46ms, 10.1MB)
ํ
์คํธ 8 ใ ํต๊ณผ (2.45ms, 10.4MB)
ํ
์คํธ 9 ใ ํต๊ณผ (2.65ms, 10.2MB)
ํ
์คํธ 10 ใ ํต๊ณผ (2.72ms, 10.2MB)
ํ
์คํธ 11 ใ ํต๊ณผ (4.55ms, 10.2MB)
ํ
์คํธ 12 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํ
์คํธ 13 ใ ํต๊ณผ (0.03ms, 10.1MB)
ํ
์คํธ 14 ใ ํต๊ณผ (0.03ms, 10.3MB)
ํ
์คํธ 15 ใ ํต๊ณผ (0.03ms, 10.2MB)
ํ
์คํธ 16 ใ ํต๊ณผ (0.01ms, 10.1MB)
ํ
์คํธ 17 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํ
์คํธ 18 ใ ํต๊ณผ (0.02ms, 10.1MB)
ํ
์คํธ 19 ใ ํต๊ณผ (0.02ms, 10MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (136.99ms, 11.9MB)
ํ
์คํธ 2 ใ ํต๊ณผ (141.49ms, 12MB)
ํ
์คํธ 3 ใ ํต๊ณผ (131.01ms, 11.8MB)
ํ
์คํธ 4 ใ ํต๊ณผ (122.39ms, 11.8MB)
ํ
์คํธ 5 ใ ํต๊ณผ (128.40ms, 11.9MB)
- ๋ค๋ฅธ ์ฌ๋๋ค ํ์ด๋ฅผ ๋ณด๋๊น, ์ํ๋ฒณ์์ผ๋ก ์ฌ์ ๋ง๋ค์ด์ ์ฐพ์์ ๋ผ์ฐ๋ ๋ฐฉ์์ผ๋ก ํ ํ์๊ฐ ์์๊ตฌ๋.
- ๊ทธ๋ฅ ๋ฌด์ง์ฑ์ผ๋ก DP ๋๋ฆฌ๋๊ฒ ๋ ๋น ๋ฅธ ๊ฑฐ์๋ค.
'๊ฒ์ ํ๋ก๊ทธ๋๋ฐ > Python ํ๋ก๊ทธ๋๋ฐ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํ๋ก๊ทธ๋๋จธ์ค ๋ํ์ค ๊ฒ์ (0) | 2023.02.15 |
---|---|
ํ๋ก๊ทธ๋๋จธ์ค ์ ์ฐ๊ธฐ (0) | 2023.02.14 |
ํ๋ก๊ทธ๋๋จธ์ค ์ธ์ฌ๊ณ ๊ณผ (0) | 2023.02.14 |
ํ๋ก๊ทธ๋๋จธ์ค ์ด๋ชจํฐ์ฝ ํ ์ธํ์ฌ (0) | 2023.02.12 |
์ฐ์ ์์ ํ๋ฅผ ํํ, ๋ํ๋ก ๋ณ๊ฒฝ (0) | 2023.02.10 |