๋‚ด ์ธ์ƒ์—์„œ ๋ฏฟ์„ ๊ฑด ์˜ค์ง ๋‚˜ ์ž์‹ ๋ฟ!

The only one you can truly trust is yourself.

๊ฒŒ์ž„ ํ”„๋กœ๊ทธ๋ž˜๋ฐ/Python ํ”„๋กœ๊ทธ๋ž˜๋ฐ

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ๋‹จ์–ด ํผ์ฆ

๐ŸŽฎinspirer9 2023. 2. 14. 05:27
728x90
๋ฐ˜์‘ํ˜•

๋‹จ์–ด ํผ์ฆ

๋ฌธ์ œ ์„ค๋ช…

๋‹จ์–ด ํผ์ฆ์€ ์ฃผ์–ด์ง„ ๋‹จ์–ด ์กฐ๊ฐ๋“ค์„ ์ด์šฉํ•ด์„œ ์ฃผ์–ด์ง„ ๋ฌธ์žฅ์„ ์™„์„ฑํ•˜๋Š” ํผ์ฆ์ž…๋‹ˆ๋‹ค. ์ด๋•Œ, ์ฃผ์–ด์ง„ ๊ฐ ๋‹จ์–ด ์กฐ๊ฐ๋“ค์€ ๊ฐ๊ฐ ๋ฌดํ•œ๊ฐœ์”ฉ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์ฃผ์–ด์ง„ ๋‹จ์–ด ์กฐ๊ฐ์ด [“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

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #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 ๋Œ๋ฆฌ๋Š”๊ฒŒ ๋” ๋น ๋ฅธ ๊ฑฐ์˜€๋‹ค.
728x90
๋ฐ˜์‘ํ˜•