[백준/Python] 20437 - 문자열 게임2

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

알파벳 소문자로 이루어진 문자열 W가 주어진다.
양의 정수 K가 주어진다.
어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.
위와 같은 방식으로 게임을 T회 진행한다.

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000)

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

예제 입력 1

2
superaquatornado
2
abcdefghijklmnopqrstuvwxyz
5

예제 출력 1

4 8
-1

첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다.

두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다.

---

풀이
맞는 풀이를 떠올렸다가 어떤 이유에선지 아니라고 판단하고 다른 방법을 찾다가 다른 사람들의 풀이를 보고 다시 돌아와서 풀었다

3번의 조건을 만족하기 위해서는 어쨌거나 문자를 k개 포함하되 그 문자가 문자열의 맨 앞과 맨 뒤 문자여야한다
4번은 3번의 조건을 만족하는 경우를 모두 훑어보면서 길이가 가장 긴 경우를 저장하면 된다

문자열에 등장하는 모든 문자들의 idx를 dict에 저장하고 그 길이가 k보다 긴 경우의 문자만 고려한다

다만 문자가 k번 이상 등장할 수도 있기 때문에 for 루프의 range를 설정하는 것에 유의해야한다

만약 "a":[0,3,7,9,15]이고, k=3 이라면 탐색을 시작할 위치는 0~len([0,3,7,9,15])-k+1 의 범위이다
그리고 해당 리스트에서 시작 위치부터 k개의 원소를 찾아야하기 때문에 탐색을 마칠 인덱스는 start_idx+k-1 이 된다

import sys

t = int(sys.stdin.readline())

for _ in range(t):
    w = sys.stdin.readline().strip()
    k = int(sys.stdin.readline())
    ans1 = sys.maxsize
    ans2 = 0

    char_dict = {}
    for idx, c in enumerate(w):
        if c not in char_dict:
            char_dict[c] = [idx]
        else:
            char_dict[c].append(idx)

    for key, val in char_dict.items():
        if len(val) >= k:
            for j in range(len(val)-k+1):
                length = val[j+k-1] - val[j] + 1
                ans1 = min(length, ans1)
                ans2 = max(length, ans2)
                
    if ans1 == sys.maxsize or ans2 == 0:
        print(-1)
    else:
        print(ans1, ans2)