[백준 20437번] 파이썬 - 문자열 게임 2

백준 20437 - 문자열 게임 2

시간 제한 1초, 메모리 제한 1024MB

# 조건

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

# 접근 방법

• 주어지는 문자열을 입력받는다.
• count라는 defaultdict를 사용하여 문자열을 탐색하며 주어지는 알파벳이 등장하는 인덱스 번호를 기록해준다.
• 이후 count 딕셔너리를 순회하며, 해당 value 값의 길이가 K보다 작다면 K개를 포함하라는 조건을 만족할 수 없으므로 continue
• K개 이상이라면, left 포인터는 0부터 시작하고, right 는 left + K -1로 시작해주며 정확하게 K개가 들어있도록 설정해준다.
  • right와 left를 동시에 1씩 늘려주어야 정확히 K개를 포함할 수 있다.
  • 이후 가장 짧은 길이와 가장 긴 길이를 갱신해주고
  • 탐색이 끝난 후 가장 긴 길이가 초기 값 0이라면 -1을 출력해준다.

from collections import defaultdict  

T = int(input())  
for _ in range(T):  
    words = input()  
    K = int(input())  
    count = defaultdict(list)  
    short_res = 99999999  
    long_res = 0  
    for i, j in enumerate(words):  
        count[j].append(i)  

    for i in count:  
        val = count[i]  
        if len(val) < K:  
            continue  
        else:  
            left = 0  
            right = left + K - 1  
            while right < len(val):  
                leng = val[right] - val[left] + 1  
                if leng < short_res:  
                    short_res = leng  
                if leng > long_res:  
                    long_res = leng  
                right += 1  
                left += 1  
    if long_res == 0:  
        print(-1)  
    else:  
        print(short_res, long_res)