백준 1593번 문자해독 | python | 슬라이딩 윈도우

문제

링크

풀이

문자열 s에 대하여 g 크기 만큼 슬라이딩 윈도우 기법으로 탐색해가며 문자열 w 와 매치하는 부분이 있으면 카운트 +1 해주면 된다.

여기서 문자열 w와 매치된다는 것은 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 의미하는데, 슬라이딩 윈도우 진행하기 전에 미리 permutations로 순열을 모두 구해두고 시작하려니 메모리초과가 발생했다.

시간복잡도가 O(n!)인데 범위가 3000이니 당연한 결과..

이에 알파벳이 등장하는 개수를 각각 세어주고 이를 탐색결과와 비교하게끔 수정해주니 통과되었다.

g,s = map(int,input().split())
w=list(input())
s=list(input())

# possible=[]
# for p in permutations(w):
#     possible.append(p) -> 이렇게 하면 메모리 초과가 뜬다.

wl=[0]*52
for i in range(len(w)):
    if ord(w[i]) >=97: # 소문자
        wl[ord(w[i])-97+26]+=1
    elif ord(w[i]) >= 65:  # 대문자
        wl[ord(w[i])-65]+=1



cnt=0
start=0
length=0
sl=[0]*52
for i in range(len(s)):
    if ord(s[i]) >=97: # 소문자
        sl[ord(s[i])-97+26]+=1
    elif ord(s[i]) >= 65:  # 대문자
        sl[ord(s[i])-65]+=1
    length+=1
    if length==g:
        if wl==sl:
            cnt+=1
        if ord(s[start]) >= 97:  # 소문자
            sl[ord(s[start]) - 97 + 26] -= 1
        elif ord(s[start]) >= 65:  # 대문자
            sl[ord(s[start]) - 65] -= 1
        start+=1
        length-=1
print(cnt)

start 변수와 length 변수 조작 잘하깅