[BOJ]1593. 문자 해독(Python) / Sliding Window

1593번: 문자 해독

W를 이루고 있는 g개의 그림문자와, 연구 대상인 벽화에 기록된 마야 문자열 S가 주어졌을 때, 단어 W가 마야 문자열 S에 들어있을 수 있는 모든 가짓수를 계산하는 프로그램을 작성하시오. 즉, 문자열  S안에서 문자열 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산하라는 뜻이다.

• 사용 알고리즘 : Sliding Window
• 처음에 순열 구하는 코드로 접근했으나 시간초과로 틀리는 것을 보고, 슬라이딩 윈도우 방식으로 접근해야한다는 것을 깨달았다.
• 슬라이딩 윈도우 방식에 아직 익숙하지 않아 다른 분의 코드를 참고했다. 설명을 잘 해놓으셨으니 참고 바란다.
• 참고 링크는  hongcoding.tistory.com/64

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

# main
wlen, slen = map(int, input().split())
w = input().strip()
s = input().strip()
wInfo = [0] * 52
sInfo = [0] * 52

for i in range(wlen):
    if 'a' <= w[i] <= 'z':
        wInfo[ord(w[i]) - ord('a')] += 1        # 소문자 처리
    else: 
        wInfo[ord(w[i]) - ord('A') + 26] += 1   # 대문자 처리

start, length, result = 0, 0, 0
for i in range(slen):
    if 'a' <= s[i] <= 'z':
        sInfo[ord(s[i]) - ord('a')] += 1
    else: 
        sInfo[ord(s[i]) - ord('A') + 26] += 1
    length += 1             # 길이 1칸 늘리기.

    # Sliding Window
    if length == wlen:      # 탐색 길이와 찾을 문자열 길이가 같으면
        if wInfo == sInfo:  # 찾는 문자열과 구성 일치
            result += 1
        if 'a' <= s[start] <= 'z':
            sInfo[ord(s[start]) - ord('a')] -= 1
        else: 
            sInfo[ord(s[start]) - ord('A') + 26] -= 1
        start += 1          # 시작 위치 1칸 밀고
        length -= 1         # 길이는 1칸 줄여준다.

print(result)

---

• 시간 : 508ms / 메모리 : 133560kb
• 고찰 : 문자열 문제를 순열(재귀 또는 itertools 라이브러리)을 사용하지 않고 슬라이딩 윈도우 방식으로 푸니까 시간초과 나지 않고 풀어낼 수 있다는 것을 알았다. 이번 네이버 코딩테스트도 이와 유사한 문제가 나왔는데, 시간초과로 터졌으리라 본다ㅠㅠ 아쉽다. 이렇게 하나 배웠으니 다음엔 절대 틀리지 말자.