[백준] 1593 문자 해독 (Python 파이썬)

www.acmicpc.net/problem/1593

1593번: 문자 해독

문제 설명

 

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

 

예를 들어, W = cAda S = AbrAcadAbRa 이라면 W로 만들 수 있는 순열이 S안에 몇개 등장하는지 세면 됩니다.

 

( 자세한 설명은 위 링크 참고 바랍니다 )

---

풀이 과정

처음에는 permutations를 이용해서 w의 모든 순열을 s와 비교하는 방식으로 풀었지만 시간초과 오류가 발생하였다.

그래서, 알파벳 52개를 배열을 이용하여 비교하는 식으로 풀었다.

 

먼저, w의 각각의 알파벳의 등장횟수를 그 알파벳에 해당하는 칸에 +1을 해줍니다.

그리고 s의 처음부터 w길이만큼 끊어서 비교를 하게되는데,

그 구간에 w와 s에 등장하는 알파벳의 횟수가 일치한다면 w의 순열로 s를 만들 수 있다는 뜻이기 때문에

정답을 +1 해주면 됩니다.

 

길이만큼 비교를 한 후에는, s의 비교 시작부분을 한 칸씩 뒤로 옮기면서 비교를 이어나갑니다.

즉, S의 1~4칸까지 비교를 했다면 다음에는 2~5칸을 비교해야 하기 때문에

비교 후에는 S의 칸을 한 칸씩 뒤로 옮겨줘야 합니다.

 

모두 비교를 한 후에 정답을 출력하면 됩니다.

 

import sys
from itertools import permutations
n, m = map(int, input().split())
w = sys.stdin.readline().strip()
s = sys.stdin.readline().strip()

wl = [0] * 52
sl = [0] * 52

# w의 각 알파벳마다 등장하는 부분 +1
for i in range(n):
    if 'a' <= w[i] <= 'z':
        wl[ord(w[i]) - ord('a')] += 1
    else:
        wl[ord(w[i]) - ord('A') + 26] += 1

start, length, count = 0, 0, 0

for i in range(m):
    if 'a' <= s[i] <= 'z':
        sl[ord(s[i]) - ord('a')] += 1
    else:
        sl[ord(s[i]) - ord('A') + 26] += 1
    length += 1

    if length == n:
        if wl == sl:
            count+=1
        if 'a' <= s[start] <= 'z':
            sl[ord(s[start]) - ord('a')] -= 1
        else:
            sl[ord(s[start]) - ord('A') + 26] -= 1
        start += 1
        length -= 1


print(count)

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !