[Gold V] 문자열 게임 2 - 20437

문제 링크

성능 요약

메모리: 31256 KB, 시간: 240 ms

분류

슬라이딩 윈도우, 문자열

문제 설명

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

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

풀이

처음에 전부 돌며 확인하도록 구현했더니 시간 초과가 났다. 그래서 문자열을 한 번 돌며 각 문자의 위치를 저장하도록 하고, 자연스레 길이도 알 수 있는 방법으로 변경하여 풀었다.

• cnum 이라는 딕셔너리에 각 문자열의 위치 리스트를 value로서 저장한다.
• cnum.values()로 cnum의 value 리스트를 돌며 K개 이상 있는 글자만 리스트를 확인한다.
• 리스트에서 K개 이상이며, 문자조건 3번(mymin)과 4번(mymax)에 맞는 답을 찾아간다.
• K==1인 경우는 그냥 빠르게 (1,1) 출력했다.

import sys
myinput = sys.stdin.readline

T = int(myinput())
for _ in range(T):
    W = myinput().rstrip()
    K = int(myinput())
    cnum = dict()
    if K == 1:
        print(1, 1)
        continue
    for i, s in enumerate(W):
        if s in cnum:
            cnum[s].append(i)
        else:
            cnum[s] = [i]
    mymin = 10001
    mymax = -1
    for x in cnum.values():
        if len(x)>=K:
            for i in range(len(x)-K+1):
                if mymin > x[i+K-1]-x[i]+1:
                    mymin = x[i+K-1]-x[i]+1
                if mymax < x[i+K-1]-x[i]+1:
                    mymax = x[i+K-1]-x[i]+1
    if mymin==10001 or mymax == -1: print(-1)
    else: print(mymin, mymax)