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

문제 출처:

www.acmicpc.net/problem/20437

20437번: 문자열 게임 2

문제 풀이 :

• 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이
  어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이
  
  를 구해야 하는 문제이다.
  
  처음엔 저 문장을 잘못 이해하여서 어떤 문자 == 해당 문자라고 생각하지 않고 풀다가 틀렸다.
• 완전탐색으로 구한다면 당연히 시간초과가 난다. 때문에 "어떤 문자"가 될 수 있는 후보군을 정한 뒤 그 후보군들의 idx들을 통해서 단어의 길이를 구했다.
• 그중에서 최대 길이 같은경우 위와 같은 조건이 존재하기 때문에 위와 같은 조건또한 추가하여서 코딩하였다.
• 풀다가 생각한거지만 결국 정답이 될 수 있는 문자열은 어떤 형식으로든지 양끝에 "어떤 문자"가 있는 문자열 일 수 밖에 없다.

import sys

input =sys.stdin.readline

t = int(input())


for test_case in range(t):
    alphabet_cnt = {'a':0,'b':0,'c':0,'d':0,'e':0,'f':0,'g':0,'h':0,'i':0,'j':0,'k':0,
                    'l':0,'m':0,'n':0,'o':0,'p':0,'q':0,'r':0,'s':0,'t':0,'u':0,'v':0,
                    'w':0,'x':0,'y':0,'z':0}
    alphabet_idx = {'a':[],'b':[],'c':[],'d':[],'e':[],'f':[],'g':[],'h':[],'i':[],'j':[],'k':[],
                    'l':[],'m':[],'n':[],'o':[],'p':[],'q':[],'r':[],'s':[],'t':[],'u':[],'v':[],
                    'w':[],'x':[],'y':[],'z':[]}
    str_arr = input()
    k = int(input())

    min_length = 1e12
    max_length = -1
    cnt =0

    for i in str_arr[:-1]:
        alphabet_idx[i].append(cnt)
        alphabet_cnt[i]+=1
        cnt+=1
    alphabet_candidate = ['a','b','c','d','e','f','g','h','i','j','k',
                    'l','m','n','o','p','q','r','s','t','u','v',
                    'w','x','y','z']

    for key,val in alphabet_cnt.items():
        if(val <k):
            alphabet_candidate.remove(key)

    #print(alphabet_candidate)
    # for i in alphabet_candidate:
    #     print(alphabet_idx[i])

    if(len(alphabet_candidate)==0):
        print(-1)
    else:
        for i in alphabet_candidate:
            temp =0
            #print(alphabet_idx[i])
            for j in range(0,len(alphabet_idx[i])-k+1):
                temp = alphabet_idx[i][j+k-1] - alphabet_idx[i][j] +1
                #print(temp,alphabet_idx[i][j],alphabet_idx[i][j+k-1])
                if(temp>max_length and str_arr[alphabet_idx[i][j+k-1]]==str_arr[alphabet_idx[i][j]]):
                    max_length=temp
                if(temp<min_length):
                    min_length =temp

        print(min_length,max_length)