백준 20437: 문자열 게임2 - 문자열(파이썬)

문자열 게임 2 성공

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을 출력한다.

 

내 코드

import sys
from collections import defaultdict

t=int(sys.stdin.readline())

for _ in range(t): #테스트 케이스 수만큼 반복.
    string=sys.stdin.readline().rstrip()
    n=int(sys.stdin.readline())
    
    dic=defaultdict(list) #key값이 없으면 빈 리스트라도 넣게하기위해! (*defulatdict*)

    for i in range(len(string)):
        if string.count(string[i])>=n: #개수가 n개 이상인 문자들에 대해서만,
            dic[string[i]].append(i) #문자별로 좌표를 저장.(ex [a]:[0, 4, 9])
 

    if not dic: #n개 이상인 문자 없으면 아예 불가능.
        print(-1)
    else:
        small=10000 #최소를 일단 최대값으로 세팅. (여기서 더 작아질 거임)
        big=1 #최대를 일단 최소값으로 세팅. (여기서 더 커질 거임)
        
        for alpha in dic: #dic에 있는 특정 문자 alpha에 대해,
            for i in range(len(dic[alpha])-n+1): #특정문자의 개수-필요한 개수+1 만큼 가능(생각해보면 아는 사실)
                length=dic[alpha][i+n-1]-dic[alpha][i]+1 #특정 문자의 좌표들간의 간격 + 1이 문자열 길이가 된다!

                #최소, 최대를 계속 최신화 시켜준다.
                small=min(small,length)
                big=max(big,length)

        print(small,big)

문자열 입력을 list()화 시켰을 때 시간초과가 난다!

풀이 및 접근)

- 모든 케이스를 훑어보려고 슬라이딩 윈도우 알고리즘을 생각했다. 구간을 바꿔가면서 구간의 첫 문자 개수가 구간이 넓어지면서 추가되면 개수를 추가하고, 그 개수가 문제에서 주어진 순간이 되었을 때 구간 길이를 저장하는 식으로 했다. 이랬더디 계속 시간초과가 떴다.

- 시간초과로 인해 풀이를 찾아 보았다. 딕셔너리를 통한 풀이가 대부분이었다. 특히 defaultdict를 사용했다.

- 특정 문자가 어느 곳에서 등장하는지를 딕셔너리를 통해 저장한다. 예를 들어 a가 1, 4, 7에 등장했고, b가 2에 등장했고, c가 5, 10에 등장했고... 등등을 저장하기 위해서이다. 이 때 defaultdict를 사용하는 이유는, 특정 문자가 처음 등장 했을 때는 그 문자와 같은 key값이 존재하지 않으므로 그 key가 null일 경우 빈 리스트라도 append하기 위해서이다. 이로써 편하게 문자별 좌표들을 저장할 수 있다.

- else문에 관한 것은 주석을 통해 이해할 수 있을 것이다.

- 또, 이번에 계속 시간초과가 나면서 알게된 사실인데, 만약 저 코드에서 string을 받을 때

sys.stdin.readline().rstrip()가 아닌, 이것에 list화를 한

list(sys.stdin.readline().rstrip()을 하게 되면, 시간초과가 난다! 문자열을 다룰 때 문자열을 리스트로 바꿔서 다루는 경우가 많은데, 이 문제에서는 그것이 시간초과를 유발했다. 시간초과시에 이 점을 한번 생각해 봐야 할 것 같다.

 

 

*참고한 블로그

https://imzzan.tistory.com/108

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