[BOJ] 9549번 암호화된 비밀번호

[BOJ] 9549번 암호화된 비밀번호 문제

굉장히 재밌었던 문제다. 난이도도 꽤 충분했고, 공부도 꽤 됐다.

---

이 문제의 핵심은 슬라이딩 윈도우(sliding window)다. 기본적인 문자열 정렬 후 비교를 할 경우 시간 초과가 나버리기 때문에, 조금 더 선형적인 시간 복잡도를 가진 알고리즘인 슬라이딩 윈도우를 사용해야 한다.

슬라이딩 윈도우는 윈도우라는 일정 칸을 잡고 미는(슬라이딩하는) 방법이다. 여기서 슬라이딩을 하는 법은 반복문을 통해 제일 뒤의 요소를 빼고 그 다음 요소를 넣으면 된다.

이렇게만 보면 은근히 투 포인터(two pointers)와 유사한 부분이 있다. 하지만 이 둘은 엄연히 다른데, 슬라이딩 윈도우는 일정한 칸을 가진 윈도우를 쭉 미는 것이라면, 투 포인터는 두 개의 포인터를 잡고 특정 조건에 따라 움직이는 것이다.

슬라이딩 윈도우와 투 포인터의 차이

---

이 문제에서 슬라이딩 윈도우를 암호화된 문자열에다가 적용을 시켜야 하며, 윈도우의 크기는 원래 비밀번호 문자열의 크기로 잡으면 된다. 하지만 1번 조건인 "비밀번호의 서로 다른 두 글자를 교환한다. 이 과정은 0번 또는 원하는 만큼 얼마든지 할 수 있다."에 의해 비교 방식을 조금 더 고민해봐야 한다.

이 문제에서는 26개의 0으로 이루어진 list를 만들고, 원래 비밀번호 문자열만큼의 길이 안에 있는 문자들의 수를 추가하고 빼는 방법을 택했다. set을 사용하기엔 수를 추가로 세어야 했기에 좋지 않았고, dict을 사용하기에도 너무 애매했기 때문에 선택했다.

import sys

if __name__ == '__main__':
    for T in range(int(sys.stdin.readline().rstrip())):
    	crypt = sys.stdin.readline().rstrip()
    	origin = sys.stdin.readline().rstrip()
    	len_crypt, len_origin, ord_a = len(crypt), len(origin), ord('a')
    	origin_list = [0 for _ in range(26)]
    	for n_o in origin:
    		origin_list[ord(n_o)-ord_a] += 1
    	is_in = False
    	crypt_list = [0 for _ in range(26)]
    	for i in range(len_origin):
    		crypt_list[ord(crypt[i])-ord_a] += 1
    	for i in range(len_origin, len_crypt):
    		if crypt_list == origin_list:
    			is_in = True
    			break

    		crypt_list[ord(crypt[i-len_origin])-ord_a] -= 1
    		crypt_list[ord(crypt[i])-ord_a] += 1

    	if crypt_list == origin_list:
    		is_in = True

    	print('YES' if is_in else 'NO')

 

조금 복잡하게 짠 감이 없잖아 있다. 처음 윈도우의 것을 설정하고, 마지막 윈도우가 for문에서 빠져버리게 if 문을 넣어서 for문이 끝난 이후에 한번 더 if문을 넣었다. 그래도 돌아가면 되는 거 아니겠는가...