문자 해독
문제
마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다.
마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다.
마야 문자 해독을 어렵게 하는 요인 중 하나는 바로 단어를 읽는 순서이다. 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에 좋게 보이도록 단어를 이루는 글자들을 아무렇게나 배열했다. 그렇기 때문에 고고학자들이 마야 기록에서 단어를 이루는 각 그림글자들의 발음을 알아내더라도 그 단어를 실제로 발음하는 방법은 정확히 알 수 없는 셈이다.
고고학자들은 W라는 특정 단어를 발굴 기록으로부터 찾고 있다. 그 단어를 구성하는 각 글자들은 무엇인지 알고 있지만, 이것이 고대 기록에 어떤 형태로 숨어 있는지는 다 알지 못한다.
W를 이루고 있는 g개의 그림문자와, 연구 대상인 벽화에 기록된 마야 문자열 S가 주어졌을 때, 단어 W가 마야 문자열 S에 들어있을 수 있는 모든 가짓수를 계산하는 프로그램을 작성하시오. 즉, 문자열 S안에서 문자열 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산하라는 뜻이다.
입력
첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실제 내용이 들어있다. 모든 문자열은 알파벳으로 이루어지며, 대소문자를 구분한다.
출력
첫째 줄에 W의 순열이 S 안에 있을 수 있는 형태의 개수를 출력한다.
풀이 방법
시도 1
시간 초과...
{알파벳:숫자}로 구성된 딕셔너리를 만들어서 비교하고자 했는데 시간 초과가 떴다.
슬라이딩 윈도우 개념을 적용하지 않아서 비교 시간이 매우 큰 것으로 보인다.
자세한 알고리즘 설명은 아래에!
import sys
g, s = map(int, input().split())
W = sys.stdin.readline().strip()
S = sys.stdin.readline().strip()
answer = 0
alphabets = {}
for x in W:
alphabets[x] = alphabets.get(x, 0) + 1
for i in range(s - g + 1):
temp = {} # 여기서 매 구간의 알파벳을 다시 카운팅하느라 시간이 많이 소요된 것으로 보임
for j in range(i, i + g):
temp[S[j]] = temp.get(S[j], 0) + 1
if temp == alphabets:
answer += 1
print(answer)시도 2
"슬라이딩 윈도우"
문자열[i:i + g]에서 문자열[i + 1:i + 1 + g]로 넘어갈 때 처음부터 알파벳을 다시 카운팅하는 것이 아니라 그 전 문자열에서 start 위치에 있던 알파벳만 빼주면 비교하는 시간을 대폭 줄일 수 있다!
알고리즘 동작 방식
1. W 문자열에 어떤 알파벳이 몇 번 나왔는지 저장해주자. 리스트 wa에 카운팅해주면 된다. ord(문자)를 이용하면 문자를 숫자(아스키코드)로 바꿀 수 있다. 이 때 영어 소문자와 대문자는 각각 65-90번, 97-122번 인데, 귀찮으니까 그냥 65-122번이라고 보고 58개 길이로 wa를 만들어 주었다. sa도 마찬가지!
2. start와 length를 0으로 초기화해주고 슬라이딩 윈도우 개념으로 S를 구간별로 검사하자. length가 찾고자 하는 문자열 W의 길이 g와 같아질 때까지 일단 sa에 알파벳을 카운팅해준다. length == g가 되면 wa와 sa를 비교해서 같은지 확인한다.
3. 다음 윈도우(구간)로 넘어가기 위해 start는 +1, length는 -1 해준다. 이 때, start 위치에 있던 알파벳을 sa에서 빼주어야 한다는 사실을 잊지 말자!
g, s = map(int, input().split())
W = input()
S = input()
answer = 0
wa = [0] * 58
sa = [0] * 58
for x in W:
wa[ord(x) - 65] += 1
# 구간 비교를 시작할 시작점 start와 현재 카운팅한 알파벳 길이 length를 초기화하고 시작한다.
start, length = 0, 0
for i in range(s):
sa[ord(S[i]) - 65] += 1
length += 1
if length == g:
if wa == sa:
answer += 1
sa[ord(S[start]) - 65] -= 1 # 이 코드를 통해 시간 복잡도를 줄일 수 있다
start += 1
length -= 1
print(answer)