백준 #20437 - [G5] 문자열 게임 2 : 슬라이딩윈도우

(python3) (17min)

20437번: 문자열 게임 2

앞으로는 시간을 재면서 풀어보기로 했다.

 

- 로 구현하는 슬라이딩 윈도우

1. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
2. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위 두 조건은 같은 조건을 가리킨다. 하나의 조건에서 최단, 최장 길이를 구하는 것이다.

 

예시 : abaccaddda, 2

위 예시에서 a만 고려하면 aba, acca, addda 가 만들어진다.

가장 짧은건 길이 3, 가장 긴건 길이 5 이다. 이 길이를 구해내는걸 a~z에 대해 수행하면 된다.

 

그럼 이 길이를 어떻게 구할 수 있을까?

a의 인덱스를 구해서 빼주면 된다.

위의 예시에서는 [0,2,5,9] 이고, K가 2이기 때문에 2-0+1, 5-2+1, 9-5+1 로 길이를 구할 수 있다.

K가 3이면 5-0+1, 9-2+1 이 된다.

 

모든 문자들에 대해 위 작업을 수행해주고 min, max값을 구해주면 된다.

 

 

코드

import sys
def solution(input) :
    # a~z에 대해서
    # 문자가 들어있는 위치 찾기
    # 1: 위치 - 위치 + 1 로 최단 길이 찾기
    # 2: 위치 - 위치 + 1 로 최장 길이 찾기

    caseN = int(input().strip())

    for _ in range(caseN) :
        S = input().strip()
        N = int(input().strip())
        alpha = [[] for _ in range(26)] # 알파벳은 26개
        
        for i in range(len(S)) : # for문 한번으로 모든 알파벳의 위치 배열을 만든다.
            alpha[ord(S[i]) - ord('a')].append(i)
        
        min_ans = 99999
        max_ans = 0
        for l in alpha :
            for end in range(N-1,len(l)) :
                start = end-N+1
                t = l[end] - l[start] + 1
                min_ans = min(min_ans, t)
                max_ans = max(max_ans, t)
        
        if max_ans == 0 : print(-1) # 조건에 맞는 경우가 하나도 없을 경우
        else : print(min_ans, max_ans) # 그외

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac