백준 20437 문자열 게임 2 Python

🐸 문제 정보

20437번: 문자열 게임 2

 

🤖 알고리즘

슬라이딩 윈도우

 

⏱️ 풀이 시간

36.01m

 

📝 풀이

문제집을 거의 다 풀어가니까 자꾸 푼 알고리즘이 겹쳐서 나오는 것 같다.

물론 이번 문제는 많이 어려웠다..! 역시 문제 이해를 잘못했기 때문이다.

특정 구간에 있는 모든 문자의 개수가 동일한 경우를 찾아야한다고 생각했다... 다시 한 번 문제를 제대로 이해해야겠다는 다짐을 했다.

 

문제를 제대로 이해하면 풀이 아이디어 자체는 크게 어렵지 않다.

1. 입력된 문자열에서 각 문자가 등장하는 인덱스를 딕셔너리에 리스트 형태로 담는다.
2. 딕셔너리에 저장된 인덱스 리스트를 탐색한다.
   1. 리스트에서 k개씩 살펴봐야하기 때문에, 마지막 탐색 인덱스는 len(list) - k + 1 이 된다.
   2. k개씩 살펴보면서, k개 내부의 시작 값과 끝 값의 차이가 곧 두 문자의 거리이다.
      • 시작점 idx
      • 끝점 idx + k - 1
   3. 이를 모두 새로운 리스트에 담는다.
3. 딕셔너리를 탐색하며 창출된 새로운 리스트에서 최소값과 최대값을 출력한다.

 

🧑‍💻 나의 답

# pypy3

import sys
from collections import defaultdict
input = sys.stdin.readline

for _ in range(int(input())):
    word = defaultdict(list)
    for idx, value in enumerate(list(input().rstrip())):
        word[value].append(idx)
    k = int(input().rstrip())
    res = []
    for idx in word.values():
        for i in range(len(idx) - k + 1):
            res.append(idx[i + k - 1] - idx[i] + 1)
    if res:
        print(min(res), max(res))
    else:
        print(-1)