[Python][백준] 20437번 문자열 게임 2

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

공부 날짜 : 2023.02.15
정답 참조 여부 : x

문자열에서 특정 문자가 k개 포함된 가장짧은 문자열의 크기와
양끝이 특정문자이고 해당 문자가 k개 포함된 가장 긴 문자열의 크기를 구하는 문제이다.

---

문제부터 이해가 되지 않는다.

특정문자를 a라고하면 주어진 문자열에서 a라는 문자가 k개 포함된 가장 짧은 부분 혹은 양끝이 a인 가장 긴 부분을 찾는 문제이다.

예시를 보면 이해가 되는데

superaquatornado
2

에서
가장 짧은 문자열은 특정 문자가 a인 경우로 aqua일때 4로 가장 짧고
양끝이 같은 가장 긴 문자열은 특정 문자가 r인 경우로 raquator일때 8로 가장 길다.

문제에 적혀있진 않지만, 가장 짧은 경우에도 양끝이 특정 문자가 되어야 가장 짧기 때문에 양끝이 특정문자인 문자열을 모두찾고 최대 최소를 구하면 된다.

---

첫번째로 전체 문자열을 돌면서 각 문자의 개수를 센다.

그다음 다시 전체 문자열을 돌면서 해당 문자가 k이상인 경우 해당 문자의 인덱스를 모두 저장한다.

마지막으로 저장된 리스트에서 해당 문자개수를 포함시켜 최대 최소를 갱신시키면 된다.

소스코드

import sys
input = sys.stdin.readline
##########################################
t = int(input())

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

    # 각 문자의 개수를 세는 딕셔너리
    count_char_dict = {}

    # 각 문자의 개수 세기
    for char in w:
        count_char_dict[char] = count_char_dict.get(char, 0) + 1

    # 결과와 관련된 변수
    check = False
    max_answer = -1
    min_answer = len(w)

    # 특정 문자열의 위치 index를 저장하는 딕셔너리
    check_dict = {}

    # 모든 문자열에 대해서
    for i in range(len(w)):
        # 해당 문자열이 k개 이하이면 다음 문자
        if count_char_dict[w[i]] < k:
            continue

        # k개 이상인 문자를 찾으면 정답이 있음
        check = True
        # 해당 문자열을 key로하고 index리스트를 value로 갖는 딕셔너리
        check_dict[w[i]] = check_dict.get(w[i], []) + [i]

    # 딕셔너리를 돌면서
    for key, value_list in check_dict.items():
        # 인덱스 번호를 바탕으로
        for i in range(len(value_list) - k + 1):
            # 최대 최소 갱신
            max_answer = max(max_answer, value_list[i+k-1] - value_list[i] +1)
            min_answer = min(min_answer, value_list[i + k - 1] - value_list[i] + 1)

    # 정답이 있으면 출력
    if check:
        print(min_answer, max_answer)

    # 없으면 -1출력
    else:
        print(-1)