20437번 문자열 게임 2

📌Problem

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

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

입력

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

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.
만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

✍solution

• 3번과 4번 진행 방식 모두 첫 번째 문자열과 마지막 번째 문자열이 동일하다는 조건
• 해당 문자열이 가능한 최대 길이와 최소 길이를 구하는 문제
• 해당 문자의 갯수를 파악하여 K개 이상인 문자열의 위치를 순서대로 딕셔너리에 정리
• 딕셔너리의 value를 순회하며 문자열의 길이 파악 - ex) 'a'라는 문자가 1,3,5,7 번째 위치에 있을 경우 K가 2라면 1~5 / 3~7의 경우가 해당 조건을 만족하는 문자열
• 문자열 길이의 최소값과 최대값을 갱신하며 문제 해결

💻Code

from collections import defaultdict
T=int(input())
for _ in range(T):
    check = [0] * 27
    word = input()
    k=int(input())

    word_dic = defaultdict(list)
    for i in range(len(word)):
        if word.count(word[i]) >= k:
            word_dic[word[i]].append(i)
    min_len=21e8
    max_len=-1
    if word_dic:
        for check_word in word_dic.values():
            for i in range(len(check_word)-k+1):
                check_len=check_word[i+k-1]-check_word[i]+1
                min_len=min(min_len, check_len)
                max_len=max(max_len, check_len)
        print(min_len,max_len)
    else:
        print(-1)