백준 1593(문자 해독) - 해결

문자 해독

 

문제

마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 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 안에 있을 수 있는 형태의 개수를 출력한다.

---

각 문자열의 순서는 상관없다는 의미이기 때문에

처음에는 그냥 리스트로 sort를 사용하여 하는 방식을 하였다.

역시나 시간 초과가 났고

이를 위해 dict를 사용하여 각 알파벳의 갯수를 계산하는 방식으로 하였다.

W의 문자열의 각 문자 갯수를 계산하고 S를 인덱싱하면서 각각 알파벳의 갯수를 갱신하면서 비교하는 방식을 사용하였다.

W의 딕셔너리는 바뀌지 않고 S의 경우 g길이만큼 잘라서 한칸씩 이동하면서 앞의 원소는 지나가면 빼지고 뒤의 원소는 더하는 방식을 사용하였고 알파벳이 없어지면 딕셔너리 자체에서 빼는 방식을 사용하였다.

그리고 다음으로 defaultdict 을 사용하여 구현해보았다.

사용 방법은 비슷하고 처음 생성방식이 다르고 다른 건 같지만 초기화 방식이 편하여 사용하기 좋다.

# 그냥 딕셔너리
import sys
input = sys.stdin.readline

# 순서는 상관없기 때문에 포함하는 알파벳 갯수를 비교하였다.

g, s = map(int,input().split())
W = list(input().strip())
# W 알파벳 딕셔너리 생성
W_dict = dict()
for w in W:
    if w in W_dict.keys():
        W_dict[w] += 1
    else:
        W_dict[w] = 1

# 처음 길이 g 만큼은 먼저 시작하기 위해 
# S 알파벳 딕셔너리 생성
S = list(input().strip())
S_dict = dict()
for ss in S[:g]:
    if ss in S_dict.keys():
        S_dict[ss] += 1
    else:
        S_dict[ss] = 1

# 비교 시작
ans = 0
# 처음 시작
if W_dict == S_dict:
        ans += 1
# 한칸씩 앞으로 가면서 비교
for i in range(g,s):
    # 앞의 알파벳을 제거하는 과정
    # 1개 있으면 딕셔너리에서 제거
    if S_dict[S[i-g]] == 1:
        del S_dict[S[i-g]]
    # 2개 이상이면 1개 제거
    else:
        S_dict[S[i-g]] -= 1
    
    # 뒤의 알파벳을 추가하는 과정
    # 딕셔너리에 있으면 1개 증가
    if S[i] in S_dict.keys():
        S_dict[S[i]] += 1
    # 없으면 1로 추가
    else:
        S_dict[S[i]] = 1
    # 두 딕셔너리 비교
    if W_dict == S_dict:
        ans += 1

print(ans)

# defaultdict 사용
from collections import defaultdict
import sys
input = sys.stdin.readline

len_w, len_s = map(int, input().split(" "))
W = input().strip()
S = input().strip()

# 초기화
W_dict = defaultdict(int)
S_dict = defaultdict(int)

# W 딕셔너리 생성
for w in W:
    W_dict[w] += 1

# 처음 S 딕셔너리 생성 
for i in range(len_w):
    S_dict[S[i]] += 1

ans = 0
if S_dict == W_dict :
    ans += 1

for i in range(len_w, len_s):
	# 앞의 알파벳 제거
    S_dict[S[i-len_w]] -= 1
    # 제거한 알파벳이 이제 없을 경우
    # 딕셔너리에서 제거
    if S_dict[S[i-len_w]] == 0 :
        del S_dict[S[i-len_w]]
    # 뒤의 알파벳 추가
    S_dict[S[i]] += 1
    
    # 비교
    if W_dict == S_dict :
        ans += 1

print(ans)