[백준 1593] 문자 해독

1. 문제

www.acmicpc.net/problem/1593

1593번: 문자 해독

2. 접근 방법

와우오아오아우와웅

 

완전 딱 처음에 봤을 때는 순열을 구하면 되겠다라는 생각을 했는데 

문자열 길이가 3000까지 되는 걸 보고 순열은 글러먹었다 라는 생각을 했다.

 

그 다음에는 그냥 word 안에 존재하는 문자일 경우에만 문자열에서 슬라이싱 해서 봐주면 되지 않을까 ? 라는 생각을 했다.

이렇게 되면 대충 가지치기 할 수 있으니까 ??

 

근데 생각해보니까 3000이면 대문자, 소문자 합쳐서 모두 52가지나 되는 문자들을 한 번씩은 다 포함하지 않을까 ???

그럼 가지치기가 의미가 없어지는 것이었따.

그리고 가지치기를 빼면 다시 현재 상태부터 그 뒤에 슬라이싱 한 부분까지 다시 카운트 세야되고 그러니까 애초에 말이 안되는 접근이었다.

 

그래서 시간초과가 진짜 많이 났다 ^-^

 

그래서 또 생각을 했다.

 

뭐였냐면

 

앞에서부터 보는데 문자열 길이만큼의 상태를 확인하는 것이다.

 

이제까지 했던 것은 그냥 문자열 있으면 보고 다시 집어넣고 뭐 이런식이었는데, 

그냥 for 반복문 가지고 현재 상태를 계속 저장하는 것이다.

 

그래서 현재 상태랑 word 상태(카운트)를 비교해서 같은지 안같은지 확인하고, 

다음 idx로 넘어가기 전에 현재 맨 앞에 있는 글자를 빼주는 것이다 => 이렇게 하면 W갯수만큼 계속 유지되니까

 

3. 코드

python

import sys

W, S = map(int, sys.stdin.readline().rstrip().split())
words = sys.stdin.readline().rstrip()
sentences = sys.stdin.readline().rstrip()
answer = 0

word_state = [0]*52
sentence_state = [0]*52
for word in words:
    if 'a' <= word <= 'z':
        word_state[ord(word)-ord('a')] += 1
    else:
        word_state[ord(word)-ord('A')+26] += 1

start, length = 0, 0

for _s in range(S):
    s = sentences[_s]
    if 'a' <= s <= 'z':
        sentence_state[ord(s)-ord('a')] += 1
    else:
        sentence_state[ord(s)-ord('A')+26] += 1
    length += 1

    if length == W:
        if word_state == sentence_state:
            answer += 1
        start_word = sentences[start]
        if 'a' <= start_word <= 'z':
            sentence_state[ord(start_word)-ord('a')] -= 1
        else:
            sentence_state[ord(start_word)-ord('A')+26] -= 1
        start += 1
        length -= 1

print(answer)

4. 마치며

생각보다 어려운 문제는 아니었는데,

내가 얼마나 시간복잡도를 생각하지 않고 구현하는지 깨달을 수 있는 계기가 되었다. 후

 

그리고 혹시나 문자열 입력받는 시간도 오래걸릴 것 같아서 

sys.stdin.readline().rstrip()으로 받았ㄸㅏ.