백준 / 문자열 게임 2 / 20437번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 문자열 게임 2 / 20437번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/20437

 

문제 설명

---

나의 풀이

from collections import defaultdict


def solve_case(word, k):
    positions = defaultdict(list)

    for idx, ch in enumerate(word):
        positions[ch].append(idx)

    min_len = float('inf')
    max_len = -1

    for ch, idx_list in positions.items():
        if len(idx_list) < k:
            continue

        for i in range(len(idx_list) - k + 1):
            start = idx_list[i]
            end = idx_list[i + k - 1]
            length = end - start + 1

            # 조건 3: 어떤 문자가 정확히 k번 포함된 가장 짧은 연속 문자열
            min_len = min(min_len, length)

            # 조건 4: 해당 문자로 시작하고 끝나는 가장 긴 연속 문자열
            if word[start] == ch and word[end] == ch:
                max_len = max(max_len, length)

    if max_len == -1:
        return "-1"
    else:
        return f"{min_len} {max_len}"


def main():
    t = int(input())

    for _ in range(t):
        word = input().strip()
        k = int(input())
        print(solve_case(word, k))


main()

---

※ 알아야 할 것

def short_search(word, k):
    short_word = float('inf')
    for i in range(len(word)):
        count = [0] * 26
        for j in range(i, len(word)):
            idx = ord(word[j]) - ord('a')
            count[idx] += 1
            if count[idx] == k:
                short_word = min(short_word, j - i + 1)
                break  # 더 짧은 건 못 나오므로 중단
    return short_word if short_word != float('inf') else -1


def long_search(word, k):
    long_word = -1

    for i in range(len(word)):
        count = [0] * 26
        for j in range(i, len(word)):
            idx = ord(word[j]) - ord('a')
            count[idx] += 1

            # 현재 윈도우 내에서 어떤 문자가 정확히 k번 등장하고,
            # 그 문자가 시작과 끝에 등장하는지 확인
            for ch in range(26):
                if count[ch] == k:
                    target = chr(ch + ord('a'))
                    if word[i] == target and word[j] == target:
                        long_word = max(long_word, j - i + 1)

    return long_word


def main():
    t = int(input())  # 테스트 케이스 수

    for _ in range(t):
        words = input().strip()
        k = int(input())
        s = short_search(words, k)
        l = long_search(words, k)

        if s == -1 or l == -1:
            print(-1)
        else:
            print(s, l)


main()

하나씩 윈도우 슬라이싱을 이용해서 찾는 방법은 시간초과되었습니다!