[백준][sliding window] 20437. 문자열게임2

20437. 문자열게임2

20437번: 문자열 게임 2

 

• 내 풀이
  • 처음에 a문자열로 k만큼 가지고 다른 값으로 처음과 끝을 가지는 문자열을 찾는 것으로 착각해서 오래걸림 
  • defaultdict으로 해당 문자열을 key로, 위치값을 value list로 넣고
  • 해당 수만큼을 포함하는 최단, 최장 길이 구하기

from collections import defaultdict

#어떤 문자를 k개 포함하는 가장짧은 문자열 길이
#포함하고, 처음, 끝이 해당문자인 가장 긴 문자열

n=int(input())
for _ in range(n):
    wlist=list(input().rstrip())
    k=int(input())
    ans1, ans2=int(1e9),0
    
    wdict=defaultdict(list)
    for idx,w in enumerate(wlist):
        wdict[w].append(idx)

    for k1,v1 in wdict.items():
        if len(v1)>=k:
            for i in range(len(v1)-k+1):
                ans1=min(ans1,wdict[k1][i+k-1]-wdict[k1][i]+1)
                ans2=max(ans2,wdict[k1][i+k-1]-wdict[k1][i]+1)
    
    if ans1==int(1e9):
        print(-1)
    else:
        print(ans1, ans2)