[BOJ] 20437번 : 문자열 게임 2(문자열, 슬라이딩 윈도우)

목차

접근

오랜만에 작성하는 글.. 인턴기간동안, 회사에서 처음 배우는 개념이나, 처음 다루는 라이브러리와 프레임워크들이 많았어서 정신없이 지나갔다... 이번년 회고글을 작성할 예정이므로 그건 나중에 차차..

 

슬라이딩 윈도우 개념으로 해결해보려고 했다.

 

접근 1

처음은 가장 단순한 접근으로 생각해보자.

이중 for문을 사용해서 window의 크기, 시작 지점을 반복해가면서 해당 범위의 문자열에 대해서 character를 카운트 해가면서 구하는 방법이 있다.

그 후 특정 문자가 `K`회 카운트 되었으면, 맞는 조건에 대해서 길이를 갱신해준다.

 

하지만 딱 봐도 반복문을 업데이트 해나가는 것과 반복마다 각 길이의 문자열에 접근해나가는 게 시간초과가 발생하기 아주 좋아보인다.

 

접근 2

매 반복마다 문자열의 character를 카운트해야할까? 생각해보니 그러지 않다.

for 문에 대해서 window의 크기가 결정되면, 처음 window에 대해서만 카운트 하고, 시작 지점을 이동할 때 마다 0번 인덱스의 character의 카운트를 -1, 마지막 인덱스의 카운트를 +1 하는 방식으로 반복을 줄일 수 있을 것이라 생각했다.

 

 

예를 들어, `superman` 이라는 문자열에 대해서, window의 크기가 3일 때

`sup` => `s` : 1, `u` : 1, `p` : 1 로 처음에 결정해주고,

그 다음 윈도우인 `upe` 를 구할 땐, 이전의 첫번째 character인 `s`의 카운트를 -1, 등장한 `e`의 카운트를 +1 해주는 방식으로 구하는 것이다.

 

하지만 이것도, 일단은 window의 크기와 각 시작지점에 대해서 전체 이중 for문을 반복해야한다는 것이 부담되기에 시간초과가 날 가능성이 크다.(실제로 시간초과가 발생)

 

접근 3

 `어떤 문자를 정확히 K개를 포함` 이라는 문장의 의미에 대해서 생각해보자.

결국 어떤 결정되지 않은 문자를 K개만 정확히 포함하면 되는 것이니까, 우리는 전체 문자에 대해서 고민하지말고 어떤 특정 문자가 발생한 범위만 고려하면 된다.

이 접근이 잘 이해가 가지 않을 수 있는데, 예를 들어서 `abbbacccca` 이런 이상한 긴문자가 있을 때, 우리가 보려고 하는 문자가 `a`라고 생각해보자.

그러면 위의 접근 처럼 각 window의 크기별로 시작지점을 모두 순회를 하면서 볼 `a`가 K개 나올 때 까지 봐야할까? 아니다 그냥 `a`가 발생한 인덱스를 가지고 보면 된다.

`a` : [0, 4, 9]

만약 우리가 `a`에 대해서 K=2를 만족하는 연속된 문자열을 찾으려고 한다면,

0 ~ 4, 4 ~ 9 에 해당하는 곳만 보면 되는 것이다. (a가 등장한 index들을 K 크기의 윈도우로 슬라이딩 윈도우 한다고 생각하면 된다.)

만약 K=3 이었다면?

0 ~ 9에 해당하는 곳만 보면 된다.

 

그렇기에 해당 방법으로, 조건에 맞는 최소 길이 문자열과 최대 길이 문자열을 전체 character에서 갱신해나가면 우리가 구하고자 하는 결과가 나올 것이다.

 

해결

1. character가 발생한 인덱스들을 모두 저장해둔다.
2. 각 character별 인덱스에 대해서 `K`크기 만큼씩 슬라이딩 윈도우를 진행한다.
3. 조건에 맞는 최소 길이 문자열과 최대 길이 문자열을 갱신한다.

코드

from collections import defaultdict

T = int(input())
for _ in range(T):
    W = input()
    K = int(input())

    len_W = len(W)
    min_len = 10_001
    max_len = 0

    char_cnts = defaultdict(list)
    for i, c in enumerate(W): # character가 발생한 인덱스를 저장
        char_cnts[c].append(i)
    
    for c, char_index in char_cnts.items():
        if len(char_index) < K:
            continue

        for i in range(len(char_index) - K + 1): # character 인덱스에 대해서 슬라이딩 윈도우를 진행
            min_len = min(min_len, char_index[i + K - 1] - char_index[i] + 1) # 최소 길이 연속 문자열
            max_len = max(max_len, char_index[i + K - 1] - char_index[i] + 1) # 최대 길이 연속 문자열

    if min_len != 10_001 and max_len != 0:
        print(min_len, max_len)
    else:
        print(-1)