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

문제 )

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

20437번: 문자열 게임 2

 

[ 풀이 IDEA ]

1. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이
2. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이

위의 2가지를 구해야한다. 

2번 뿐만 아니라, 1번을 구할 때에도 문자열의 앞뒤가 같은 문자여야만 한다. 그렇기 때문에, 1/2번은 한번에 구해주면 된다!

dictionary이용해서 문제를 풀었다.

1️⃣ 문자열에서 K개 이상 존재하는 알파벳만 dictionary에 위치를 저장해주었다.

(key: 알파벳 , value : 알파벳 위치 인덱스 list를 저장)

2️⃣ K개 이상 존재하는 알파벳의 index들(dictionary의 value값) 만 검색하면서 해당문자를 K개 포함하는 문자열 길이를 구해준다.

ex. idx_list = [1, 3, 9], K = 2  👉 [1, 3], [3, 9] 의 길이를 구해줘야한다. 

3️⃣ 가장 짧은 연속 문자열/ 가장 긴 연속 문자열인지 확인하고 update

 

- python code 

from collections import defaultdict

def solution(line):
    alpha_dict = defaultdict(list)    
    max_len = 0
    min_len = 1e9

    # 문자열에서 K개 이상 존재하는 알파벳만 dictionary에 위치 저장
    for i in range(len(line)):
        if line.count(line[i]) >= K:
            alpha_dict[line[i]].append(i)
    
    # K개 이상 존재하는 알파벳이 없는 경우
    if not alpha_dict:
        return (-1,)

    # 해당문자를 K개 포함하는 문자열 길이를 구하기
    for idx_list in alpha_dict.values():
        for j in range(len(idx_list)-K+1):
            alpha_len = idx_list[j+K-1] - idx_list[j] + 1
            
            max_len = max(max_len, alpha_len)
            min_len = min(min_len, alpha_len)

    return min_len, max_len           


T = int(input())
for _ in range(T):
    line = input()
    K = int(input())
    print(*solution(line))