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

문제 링크

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

20437번: 문자열 게임 2

 

문제 풀이

1. 주어진 문자열에서 k개 이상 문자를 포함하는 문자의 위치를 뽑아 list 형태로 dictionary에 넣어준다.
2. 1번 결과로 나온 dictionary의 list를 시작 인덱스부터 k개까지 범위를 잡을 수 있는 만큼 순회한다.
3. 해당 범위의 마지막 인덱스에서 처음 인덱스까지의 차를 저장하여 min, max값을 도출한다.  

 

전체 코드

from collections import defaultdict

num = int(input())

'''
입력 예시:
abaaaba
3
'''

for _ in range(num) :
    w = input().strip()
    k = int(input())

    alpha = defaultdict(list)
    for i in range(len(w)) :
        if w.count(w[i]) >= k :
            alpha[w[i]].append(i)	# alpha = {'a': [0, 2, 3, 4, 6]}

    if alpha :
        result = []
        for alpha_list in alpha.values() :	# alpha_list = [0, 2, 3, 4, 6]
            for i in range(len(alpha_list)-k+1) :	# 3번 순회: (0~3), (2~4), (3~6)
                result.append(alpha_list[i+k-1] - alpha_list[i] + 1)
        print(min(result), max(result))
    else :
        print(-1)