[Python] BOJ(백준) 1593 문자 해독

https://www.acmicpc.net/problem/1593

 

투 포인터 문제라고 분류 했지만, 정확히는 슬라이딩 윈도우 문제다.

 

문자열 W의 순서를 바꾸어(순열) 만들 수 있는 문자열이 문자열 S에 몇 개 포함되어 있는지 카운팅하는 문제다.

 

가장 먼저 떠오른 방법은 W의 길이만큼 슬라이딩 윈도우를 진행하는 것이다.

S의 문자열을 W의 길이만큼 잘라서(S') 정렬한 뒤 정렬된 W와 같은지 비교하는 것이다.

어림도 없지. 시간 초과다. 작게 나마 시간을 줄여보려 했으나 안된다.

 

그래서 질문 게시판에서 힌트를 얻었고, 글자 수를 카운트 하는 아이디어를 얻었다.

그러나 생각이 짧은 나머지,,, 문자열을 잘라서 각각의 문자 개수를 매번 계산했다.

심지어 Counter 함수를 이용했는데 이러면 딕셔너리로 반환이 되기 때문에 딕셔너리 연산을 해야한다.

딕셔너리의 비교보다 리스트의 비교가 시간이 덜 걸린다고 한다.

딕셔너리와 상관없이 시간 초과는 당연한 일이다.

 

열심히 고민하던 끝에 슬라이딩 윈도우의 개념을 다시 복기하게 되었다.

한 칸 씩 움직이기 때문에 슬라이딩이 진행되면 맨 앞 한 글자만 빠지고, 맨 뒤 한 글자만 추가된다.

이 점을 이용하여 중복되는 부분들은 계산하지 않고, 변화하는 부분들만 체크했다.

 

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
w = input().strip()
s = input().strip()
lw = len(w)
ls = len(s)

lstw = [0 for _ in range(52)]
lsts = [0 for _ in range(52)]

for i in range(lw):
    ww = ord(w[i])
    ss = ord(s[i])
    if ww < 97:
        lstw[ww - 65] += 1
    elif ww > 96:
        lstw[ww - 97 + 26] += 1

    if ss < 97:
        lsts[ss - 65] += 1
    elif ss > 96:
        lsts[ss - 97 + 26] += 1

res = 0
if lstw == lsts:
    res += 1
    
for i in range(lw, ls):
    a = ord(s[i - lw])
    b = ord(s[i])
    
    if a < 97: lsts[a - 65] -= 1
    elif a > 96: lsts[a - 97 + 26] -= 1

    if b < 97: lsts[b - 65] += 1
    elif b > 96: lsts[b - 97 + 26] += 1

    if lstw == lsts:
        res += 1
        
print(res)

 

다만, 알파벳과 아스키코드를 이용하는 점이 파이썬에서는 순조롭게 진행되지 않았다...

그 놈의 str과 int는 연산이 불가능하다는 에러.....................

모두 숫자로 바꿔 연산을 진행했다.

 

더 효율적인 코드가 존재할 것 같다.