[BOJ][🟡5][백준#20437] 문자열 게임 2

문제 출처

BAEKJOON Online Judge #20437

문제

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

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

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

입력

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

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다. 만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

예제

예제 1

입력

2
superaquatornado
2
abcdefghijklmnopqrstuvwxyz
5

출력

4 8
-1

예제 2

입력

1
abaaaba
3

출력

3 4

My Sol

def check(txt):
    D = {}
    l = len(txt)
    for i in range(l):
        t = txt[i]
        if not D.get(t, []):
            D[t] = []
        D[t].append(i)
    return D

def check_length(D, K):
    ret = [1e5, 0]
    for arr in D.values():
        l = len(arr)
        if l < K: continue
        for i in range(l-K+1):
            gap = arr[i+K-1]-arr[i]+1
            if ret[0] > gap: ret[0] = gap
            if ret[1] < gap: ret[1] = gap

    return [-1] if ret == [1e5, 0] else ret

T = int(input())
for _ in range(T):
    txt = input()
    K = int(input())
    D = check(txt)
    ret = check_length(D, K)
    print(*ret)

간단하게 해결할 수 있는 문제였다.

1. 각 테스트케이스마다 주어지는 텍스트를 확인한다.
2. 텍스트의 각 문자마다 딕셔너리에 index를 넣어 배열로 표시한다. 나는 check 함수에서 txt를 받아 index들을 값으로 하는 D 딕셔너리를 return해주었다.
3. 최소 K개를 포함하는 문자열의 최소길이와 최대길이를 확인해야 하므로, D의 각 array마다 K-1 개의 gap으로 index의 차이를 확인하여 최대최소를 구한다. 나는 이를 check_length 함수 내에서 처리해주었다. 최초 초기화는 [최소, 최대]인 경우 [1e5, 0]으로 초기화하고 이와 대조하여 변경, 갱신하는 방식이다.
4. 만약 K개를 포함하는 array가 하나라도 없으면 ret은 [1e5, 0]이므로 [-1]을 return하고 아니라면 최대최소가 반영된 ret을 return한다.
5. check_length 함수의 반환값을 spread하여 출력한다.

결과

맞았습니다!!