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

문제 링크 : https://www.acmicpc.net/problem/20437

20437번: 문자열 게임 2

 

---

문제

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

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

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

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000) 

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

 

예제 입력 : 

2
superaquatornado
2
abcdefghijklmnopqrstuvwxyz
5

예제 출력 :

4 8
-1

 

코드

import sys
from collections import defaultdict
input = sys.stdin.readline
T = int(input())
W = ['']*T
K = [0]*T

for a in range(T):
    W[a] = input()
    K[a] = int(input())

def game(w, k):
    if k == 1:
        return 1, 1
    else:
        length = len(w)
        minimum = length
        maximum = 0
        string_input = defaultdict(list)

        for j in range(length):
            if w.count(w[j]) >= k:
                string_input[w[j]].append(j)

        if not string_input:
            return -1,

        for z in string_input.values():
            for y in range(len(z)-k+1):
                abs_jz = z[y+k-1]-z[y]+1
                if maximum < abs_jz:
                    maximum = abs_jz
                if minimum > abs_jz:
                    minimum = abs_jz

        return minimum, maximum

for i in range(T):
    print(*game(W[i], K[i]))

 

+ 기억해두기 

1. 배열 초기화 시간 절약 
W = []
K = []
하고 append 하는 것 보다

W = ['']*T
K = [0]*T
이렇게 미리 초기화 해두고 대입하는 것이
시간이 덜 걸린다고 한다!

2. 두 쌍 return 함수 괄호 없애기
내 코드의 경우 max와 min 값을 동시에 return 하기 때문에 
그냥 print(함수)를 하게 되면
(4, 8) 이런식으로 출력이 된다.
괄호 없이 출력하려면 앞에다가 *을 붙이면 된다!

print(*game(W[i], K[i]))

 

+ TMI

하.. 아주 머리아픈 문제였다.
나는 K개 이상 있는 문자에 대해서 for 문 돌릴 때 바로 앞에 것들을 훑으면서
개수 K개 센 다음에 문자길이를 계산하는 형식으로 코딩을 했는데..

하염없이 시간 초과~~~~
ㅠㅠㅠㅠㅠㅠㅠㅠㅠ

온갖 방법으로 코드를 간추려봤는데도
계에속 시간초과가 떴다.......

물론 나의 역량 부족이 맞지만....

어우 안되겠어서
결국 다른 방법을 사용했다ㅠㅠㅠㅠ

사전에 K개 이상인 알파벳들을 넣어두고 value로는 그 알파벳이 있는 인덱스를 넣는다.
그래서 그 value 안에서 문자 길이를 계산하는 것이다! 

겨우겨우 고생끝에 

맞았습니다!!
를 봤다..
어휴.. 이 문제는 나중에 다시 풀어봐야 할 것 같다.

 

흑..앞으로도 화이팅...!!