[Baekjoon] 1593 문자 해독 Python

 

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

1593번: 문자 해독

 

첫 시도)

permutations 를 이용해서 풀려고 했으나 시간초과가 떴다.

그래서 계속 생각하다가 결국 정답 코드를 참고했다.

 

import sys
fastin = sys.stdin.readline()

w, s = map(int, fastin.split())
words = input().strip()
sentences = input().strip()


wordList = [0]*52
sentenceList = [0]*52

for word in words:
    if 'a' <= word <= 'z':
        wordList[ord(word) - ord('a')] += 1
    else:
        wordList[ord(word) - ord('A') + 26] += 1

start, length, count = 0, 0, 0

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

    if length == w:
        if wordList == sentenceList:
            count += 1
        if 'a' <= sentences[start] <= 'z':
            sentenceList[ord(sentences[start]) - ord('a')] -= 1
        else:
            sentenceList[ord(sentences[start]) - ord('A') + 26] -= 1
        start += 1
        length -= 1

print(count)

 

 

포인트는

1) a~z, A~Z 수 만큼의 길이를 가진 wordList와 sentenceList를 만들어서 비교하는 것

2) 찾을 문자는 sentences안에 순서만 바꼈을 뿐 연결되어 있다. (문제 잘 이해하고 풀자.)

 

이 방법은 혼자 머리를 싸메도 생각 못해냈을 것 같다.

알고리즘 문제 풀면서 계속 안풀리면 다른 코드 참고하기 ✔

 

계속 런타임 오류가 떠서 수정을 했었는데,

1) wordList[ord('a') - ord(word)] += 1

이렇게 연산의 좌우를 바꿔 썼었다.

 

2) 입력받는 부분에서 words와 sentences를 입력받을 땐 fastin을 사용하면 w, s에 입력한 값이 입력되었다. 왜지??? 이건 스터디 때 알아보는 걸로

 

몇 번씩 더 보면서 내껄로 만들기 ✔

 

참고한 글 : https://maeng2world.tistory.com/128