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

20437번: 문자열 게임 2

 

 

 

코드

import sys
from collections import defaultdict

def length(dic):
	min_l = 10000
	max_l = 0
	for i in dic:
		for j in range(len(dic[i])-k + 1):
			length = dic[i][j+k-1] - dic[i][j] + 1
			min_l = min(min_l,length)
			max_l = max(max_l,length)
	return(min_l,max_l)
			
t = int(sys.stdin.readline())
for _ in range(t):
	word = sys.stdin.readline().strip()
	k = int(input())
	dic = defaultdict(list)
	for i in range(len(word)):
		if word.count(word[i]) >= k:
			dic[word[i]].append(i)
	if not dic:
		print(-1)
	else:
		print(*length(dic))

 

설명

입력받은 문자열에서 k개 이상 존재하는 문자만 해당 문자의 위치와 같이 딕셔너리에 저장했다. 

이때 defaultdict를 사용했다. defaultdict는 key값이 없을 경우 미리 지정해놓은 초기값을 반환하는 딕셔너리다. 이 문제에서는 초기값을 list로 했다.

만약 defalutdict를 사용하지 않으면 dic[word[i]].append(i)를 할 때 word[i]가 key로 존재하지 않는 경우 오류가 발생한다. 

 

 

파이썬 collections defaultdict에 대해 간단히 알아봅시다.

 

dic[i][j+k-1]  - dic[i][j] + 1로 어떤 문자를 k개 포함하는 문자열의 길이를 구한 후 max_l과 min_l의 값을 계속 갱신해줬다.