[백준] 20437: 문자열 게임 python 구현

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

 

풀이

1. k번 이상 등장한 문자열에 대해서 key를 문자로 갖고, value를 index list를 갖는 문자열 리스트를 만든다.
   • ex) {'a': [1, 2, 13], 'b': [4, 7], ....}
2. dict를 순회하며 문제 3번과 4번을 만족하는 정답을 찾는다.
   1. index list가 k개 일때와 k개 초과일때 두 가지를 탐색하여야 한다.
   2. 문제 3번은 특별한 조건은 없어도 가장 짧은 길이를 위해서는 앞과 뒤가 같은 문자열이어야 한다.

 

CODE

import sys
from collections import defaultdict
t = int(input())
for _ in range(t):
    w = sys.stdin.readline().strip()
    k = int(input())

    # key: 문자, value: index list   |   ex) a: [1, 12]
    char_dict = defaultdict(list)
    for idx, char in enumerate(w):
        if w.count(char) >= k: # k번 이상 나온 char에 대해
            char_dict[char].append(idx)

    short = 10e7
    long = 0
    for char, idx_list in char_dict.items():
        # 정확히 k개 포함
        if len(idx_list) == k:
            length = idx_list[-1] - idx_list[0] +1
            if length < short:
                short = length
            if length > long:
                long = length

        # index list가 k개 보다 클 때 
        elif len(idx_list) > k:
            st = 0
            while 1:
                nd = st + (k-1)

                length =  idx_list[nd] - idx_list[st] + 1

                if length < short:
                    short = length
                if length > long:
                    long = length
            
                if nd == (len(idx_list)-1):
                    break
                
                st += 1

    if not long and short > 10000:
        print(-1)
    else:
        print(short, long)