[백준] #20437 문자열 게임2(python)

📌문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000)

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

예제 입력1

2
superaquatornado
2
abcdefghijklmnopqrstuvwxyz
5

예제 출력1

4 8
-1

예제 입력2

1
abaaaba
3

예제 출력2

3 4

백준 20437번 문제

💡Idea

문자열 게임🎮의 3번과 4번에서 구하는 연속 문자열의 길이는 각각 다음과 같은 의미를 가집니다.

• 3번 : 어떤 문자가 위치한 인덱스 k개 중, 처음 인덱스와 마지막 인덱스의 차이가 가장 짧은 길이
• 4번 : 어떤 문자가 위치한 인덱스 k개 중, 처음 인덱스와 마지막 인덱스의 차이가 가장 긴 길이

3번의 경우, 어떤 문자 A가 정확히 k개가 포함된 문자열 중 가장 짧은 문자열을 찾으려면 당연히 해당 문자열의 맨 앞과 맨 뒤 문자가 A여야 합니다.

4번의 경우에는, 정의 자체가 첫 번째와 마지막 글자가 해당 문자로 같아야 한다고 나와있기 때문에 당연히 A.....A(A의 개수는 총 k개)의 형태를 가지게 됩니다.

처음에는 4번의 정의가 헷갈렸었는데, 어떤 문자 A가 정확히 k개이면서 문자열의 맨 처음과 끝이 각각 A인 문자열의 길이를 찾는 것으로 생각하면 쉽게 그 의미를 깨달을 수 있습니다.

💻코드

• ⏰ 시간 : 188 ms / 메모리 : 31256 KB

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    w = input().strip()
    k = int(input())
    alpha_dic = {alpha : [] for alpha in set(w)}
    length_set = set()
    
    for i in range(len(w)):
        alpha_dic[w[i]].append(i)
    
    for index_list in [alpha_dic[alpha] for alpha in alpha_dic if len(alpha_dic[alpha]) >= k]:
        for i in range(len(index_list) - k + 1):
            length_set.add(index_list[i + k - 1] - index_list[i])
    
    if length_set:
        print(min(length_set) + 1, max(length_set) + 1)
    else:
        print(-1)

📝코드 설명

변수

• alpha_dic : 문자열에 속한 각 알파벳이 key, 해당 알파벳이 위치한 인덱스 리스트가 value
• length_set : 어떤 문자가 k개 속한 문자열의 모든 길이 집합

알고리즘

1. 입력받은 문자열 w에 속하는 각 알파벳들의 개수가 k개 이상인 것들을 찾습니다.

2. 각 알파벳이 정확히 k개가 속하도록 하는 인덱스 두 개의 길이 차이들을 length_set에 추가해줍니다.

3. length_set에서 가장 작은 값이 3번의 답, 가장 큰 값이 4번의 답이 됩니다.

4. 만약 length_set에 아무 값도 없다면, k개 이상인 문자가 없어 만족하는 문자열을 찾을 수 없다는 뜻이므로 -1을 출력해줍니다.