[백준] 24037 문자열게임2 / 구현 / python 골5

보자마자 슬라이딩 윈도우라는 생각

 

https://www.acmicpc.net/submit/20437

 

처음에는 '20922_겹치는 건 싫어'의 풀이를 응용해보려고 했다

이 풀이는 어떤 문자를 k개 이하로 포함하는 가장 긴 부분 수열을 구하는 문제

 

그래서 이걸 응용해서 어떤 문자를 정확히 k개 포함하는 가장 짧은 부분 수열을 구하는 것까지는 괜찮았다

근데 어떤 문자를 k개 포함하면서, 처음과 끝이 그 문자로 이뤄진 수열을 구하는 부분에서 좀 오차가 있었다

 

<틀린 풀이>

from collections import defaultdict
t = int(input())
for i in range(t):
    a = list(map(str, input().strip()))
    k = int(input())

    n = len(a)
    #어떤 문자를 k개 포함하는 가장 짧은 연속 문자열의 길이
    #어떤 문자를 k개 포함하고, 시작-끝 문자가 해당 문자인 문자열
    #없으면 -1

    count = defaultdict(int)
    start = 0
    min_l = float('inf')

    for end in range(n):
        count[a[end]] += 1
        while count[a[end]] == k:
            min_l = min(min_l, end-start+1)
            count[a[start]] -= 1
            if count[a[start]] == 0:
                del count[a[start]]
            start += 1
    
    count_max = defaultdict(int)
    start_max=0
    max_l = 0
    for end in range(n):
        count_max[a[end]] += 1
        while count_max[a[end]] >= k:
            if count_max[a[end]] >= k and a[end] == a[start_max]:  # 시작과 끝 문자가 동일해야 함
                max_l = max(max_l, end - start_max + 1)
            count_max[a[start_max]] -= 1
            if count_max[a[start_max]] == 0:
                del count_max[a[start_max]]
            start_max += 1
    if min_l==float('inf') or max_l==0:
        print(-1)
    else:
        print(min_l, max_l)

 

어찌되었든

다른 방법으로 해결하자

 

문자열 탐색 가능 여부 flag은 found boolean 변수로 탐색

 

문자열을 set처리하면 중복 원소 없이 문자 종류만 남는다

 

문자열을 for문 돌려서 어떤 문자가 나오는 위치를 indices 리스트에 저장한다

해당 문자가 k번 이상 나오지 않으면 pass

 

만약 k번 이상 존재하면 조건에 맞는 문자열을 만들 수 있기 때문에 탐색 시작

found값도 True로 바꿔준다

 

최단부분수열 구하기

- indices에 문자의 index가 저장되어 있으니까, 이 위치를 적절히 k개만 포함하도록 for문을 돌린다

- indices 배열에서 연속된 index값을 k개 묶으면서 봐야함

  - 탐색 범위는 0부터 배열길이-k+1까지만 확인하면 된다 (배열길이-k+1번째에서 k개 탐색하면 끝까지 탐색하게 되니깐)

- 현재 위치에서 k개 위치를 묶었을 때 i+k번째 index값과 i번째 index값의 차이로 길이를 구한다

- 이전 최소 길이값이랑 min 비교해서 업데이트

 

최장부분수열이면서 시작,끝 값이 어떤 문자로 동일

- 여기에는 i번째와 i+k번째 index값이 set 안에 어떤 문자와 동일한 경우에만 탐색한다

- 길이는 마찬가지로 i+k번째에서 i번째 index값을 빼서 구한다

- 이전 최장 길이 값이랑 max비교해서 업데이트

 

만약 위 조건에 해당하는 문자열이 없으면 found값이 여전히 False일 것이고 -1출력

그 외에는 min길이, max길이 순으로 출력

 

from collections import defaultdict

t = int(input())
for _ in range(t):
    w = input().strip()
    k = int(input())

    n = len(w)
    min_length = float('inf')
    max_length = 0
    found = False

    # 각 문자에 대해 처리
    for char in set(w):
        indices = [i for i, c in enumerate(w) if c == char]
        if len(indices) < k:
            continue

        found = True

        # 최소 길이 계산
        for i in range(len(indices) - k + 1):
            length = indices[i + k - 1] - indices[i] + 1
            min_length = min(min_length, length)

        # 최대 길이 계산
        for i in range(len(indices) - k + 1):
            if w[indices[i]] == char and w[indices[i + k - 1]] == char:
                length = indices[i + k - 1] - indices[i] + 1
                max_length = max(max_length, length)

    if not found:
        print(-1)
    else:
        print(min_length, max_length)