[백준] 20437 문자열 게임 2 (파이썬 python)

 

문제 링크

 

https://www.acmicpc.net/problem/20437

20437번: 문자열 게임 2

 

 

문제 풀이

 

총 2가지를 구해야하는데, 주어진 양의 정수 k개만큼 특정 문자를 포함하는

가장 짧은 문자열의 길이와 가장 긴 문자열의 길이를 구해야 합니다.

최소 길이가 되려면 어차피 문자열의 첫 번째와 마지막 글자가 k개에 포함되는 특정 문자여야 합니다.

결국 처음과 마지막 글자가 특정 같은 문자인 문자열을 구하되 최소길이와 최대길이를 구하면 되는 것입니다.

 

문제를 해결하기 위해 defaultdict(list) 형태로 딕셔너리를 만들어준 후,

문자열 내의 전체 문자를 key : 문자열, value : index의 리스트 형태로 추가해줍니다.

 

dic = defaultdict(list)
for i in range(len(word)):
    dic[word[i]].append(i)

 

 

이후 모든 키에 대한 value 값을 확인했을 때, value 값인 리스트의 길이가 k 이상인 것들에 대해서만

슬라이딩 윈도우 알고리즘을 활용하여 k 길이만큼 잘라내어 인덱스값의 차이를 통해 길이를 구합니다.

어차피 결과값으로 도출되는 문자열은 처음과 마지막이 같은 문자이므로

k 길이만큼 잘라낸 배열의 가장 마지막 값에서 가장 처음 값을 뺀 것이 해당 문자열의 길이가 됩니다.

이렇게 나온 문자열의 길이를 전역 변수로 저장한 min_len, max_len 값과 비교해가며 갱신하여 줍니다.

 

min_len = 1e9	
max_len = -1
for key in dic.keys():
    arr = dic[key]
    if len(arr) >= k:
        for i in range(len(arr) - k + 1):
            length = arr[i + k - 1] - arr[i]
            min_len = min(min_len, length)
            max_len = max(max_len, length)

 

 

전체 코드

 

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

t = int(input())
for _ in range(t):
    word = input()
    k = int(input())
    dic = defaultdict(list)
    min_len = 1e9
    max_len = -1
    for i in range(len(word)):
        dic[word[i]].append(i)
    for key in dic.keys():
        arr = dic[key]
        if len(arr) >= k:
            for i in range(len(arr) - k + 1):
                length = arr[i + k - 1] - arr[i]
                min_len = min(min_len, length)
                max_len = max(max_len, length)
    if min_len == 1e9:
        print(-1)
    else:
        print(min_len + 1, max_len + 1)