백준 1593 문자 해독(python, 슬라이딩 윈도우)

취준 너무 싫다.....

 

* 문제 링크: https://www.acmicpc.net/problem/1593

1593번: 문자 해독

 

* 해결과정: 슬라이딩 윈도우 방식 활용

1. 첫 번째 변수는 word, 두 번째 변수는 sentence로 정의

2. 소문자와 대문자의 개수(26 * 2)만큼의 크기를 가진 리스트 2개 생성

 - 각각을 word_state, sentence_state로 정의

3.  word의 각 문자를 소문자는 0~25번, 대문자는 26~51번 인덱스에 개수만큼 저장

 - ex) cAda 이면, [1, 0, 1, 1, 0, ...] 이런 식으로

4. sentence의 길이만큼 하단을 반복

 1) 각 문자를 sentence_state에 저장

 2) length가 word 길이만큼 되면 sentence_state==word_state 여부 확인

 3) 2)가 참이면 result+=1

 4) 2)가 거짓이면, sentence_state의 첫 번째로 저장된 문자의 개수를 -1 처리

 5) 4)가 완료되면, length는 -=1

 

import sys W, S = map(int, sys.stdin.readline().rstrip().split()) word = sys.stdin.readline().rstrip() sentence = sys.stdin.readline().rstrip() sol = 0 word_state = [0]*52 sentence_state = [0]*52 for w in word:     if 'a' <= w <= 'z':         word_state[ord(w)-ord('a')] += 1     else:         word_state[ord(w) - ord('A')+26] += 1          length = 0; start = 0 for w in sentence:     if 'a' <= w <= 'z':         sentence_state[ord(w)-ord('a')] += 1     else:         sentence_state[ord(w) - ord('A')+26] += 1     length += 1          if length == len(word):         if word_state == sentence_state:             sol += 1              length -= 1         if 'a' <= sentence[start] <= 'z':             sentence_state[ord(sentence[start])-ord('a')] -= 1         else:             sentence_state[ord(sentence[start]) - ord('A')+26] -= 1                      start += 1 print(sol)

 

* 관련 추천문제: 백준 3078 좋은 친구