[백준 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 안에 있을 수 있는 형태의 개수를 출력한다.

---

접근

처음에 입력받은 W에 대해 만들 수 있는 모든 문자열을 만든 후에 비교하였다. 하지만 W의 최대 길이가 3000이기 때문에 해당 경우의 수를 모두 만드는데에도 많은 시간이 걸릴 것이다. 풀기 전에 입출력을 확인하고 시간복잡도를 어느정도 파악해야하는 습관을 길러야겠다.

 

이후 다른 사람들의 풀이를 참고하였고

W에 대해 각 문자의 카운터 리스트를 만들고 S에 대해 슬라이딩 윈도우를 하면서 카운터 리스트를 만들어준다.

이후 두 개의 카운터 리스트를 비교하여 각 문자의 인덱스에 해당하는 값이 모두 같을 때 최종해를 증가시키도록 하였다.

 

구현

- 먼저 입력받은 W의 각 알파벳이 얼마나 나왔는지 alpha_list에 기록한다.

- 이후 횟수가 1이상인 알파벳의 인덱스를 check_index에 기록하여 해당 인덱스들만 비교할 수 있도록한다.

for w in word:
    alpha_counter[ord(w) - ord('A')] += 1

for k, v in enumerate(alpha_counter):
    if v > 0:
        check_index.append(k)

- 이제 문자열 S에 대해서 슬라이딩 윈도우를 진행한다.

- W길이 만큼 deque에 저장했을 때 check_index에 있는 인덱스들을 모두 비교한다.

- 이 때 횟수가 다를 경우는 flag를 False로 변경 후에 break하여 탐색을 종료한다.

- 탐색 종료 후에 flag가 True라면 최종해를 증가시킨다.

answer = 0
dq = deque()
counter = [0] * 58
for k, v in enumerate(maya_word):
    dq.append(v)
    counter[ord(v) - ord('A')] += 1
    if k < W - 1:
        continue

    flag = True
    for check in check_index:
        if alpha_counter[check] != counter[check]:
            flag = False
            break
    if flag:
        answer += 1

    w = dq.popleft()
    counter[ord(w) - ord('A')] -= 1

print(answer)

---

전체 코드

import sys
from _collections import deque
input = sys.stdin.readline


W, S = map(int, input().split())
word = list(input().strip())
maya_word = list(input().strip())
alpha_counter = [0] * 58
check_index = []

for w in word:
    alpha_counter[ord(w) - ord('A')] += 1

for k, v in enumerate(alpha_counter):
    if v > 0:
        check_index.append(k)

answer = 0
dq = deque()
counter = [0] * 58
for k, v in enumerate(maya_word):
    dq.append(v)
    counter[ord(v) - ord('A')] += 1
    if k < W - 1:
        continue

    flag = True
    for check in check_index:
        if alpha_counter[check] != counter[check]:
            flag = False
            break
    if flag:
        answer += 1

    w = dq.popleft()
    counter[ord(w) - ord('A')] -= 1

print(answer)