[ BAEKJOON ] 문자열 게임 2 / 20437 / 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

첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다.

두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다.

예제 입력 2

1
abaaaba
3

예제 출력 2

3 4

 

---

 

나의 풀이

로직

사실 문제를 한번만에 이해하진 못했다..ㅎ

예제를 보니 문제를 이해할 수 있었고, 대충 어떻게 풀어야하는지 감이 왔다.

문자열에 포함된 문자를 “인덱스화”하여 딕셔너리에 저장한다면 각 문자가 포함된 문자열의 길이를 파악하기가 정말 쉬울 것이라고 접근했다.

우선 superaquatornado를 예시로 들어서 설명해보자면,

각각의 문자를 key값으로 가지고 각 문자의 인덱스 번호를 value로 배열로 가지고 있도록 해보자.

s [0]
u [1, 7]
p [2]
e [3]
r [4, 11]
a [5, 8, 13]
q [6]
t [9]
o [10, 15]
n [12]
d [14]

이 중 문자를 정확히 k개 포함하는 지는 value의 길이를 파악하면 된다.

예시의 k는 2개이므로 2개이상이 되는 value만 뽑아보자.

u [1, 7]
r [4, 11]
a [5, 8, 13]
o [10, 15]

여기서 정확히 k개를 포함하는 문자열의 길이는 2개를 간격으로 두고 뒷 번호에서 앞 번호를 빼준 뒤 1를 더하면 해당 문자열의 길이가 된다.

u [1, 7] -> 7
r [4, 11] -> 8
a [5, 8, 13] -> 4, 6
o [10, 15] -> 6

이렇게 7, 8, 4, 6, 6 이라는 어떤 문자를 정확히 k개 포함하는 문자열의 길이를 구할 수 있다.

이 중 가장 작은 길이와 가장 긴 길이가 우리가 구하고자 하는 것이다.

 

 

코드

from collections import defaultdict 

tc = int(input())

for _ in range(tc):
    word = input()
    k = int(input())
    
    alphabet_dict = defaultdict()

    for i, w in enumerate(word):
        if alphabet_dict.get(w) == None :
            alphabet_dict[w] = [i]
        else:
            alphabet_dict[w].append(i)

    for (key, value) in alphabet_dict.items():
        if len(value) >= k:
            for i in range(0, len(value) - k + 1):
                tmp.append(value[i + k - 1] - value[i] + 1)

    if tmp == []:
        print(-1)
    else:
        print(min(tmp), max(tmp))

위의 코드를 최적화한다면

from collections import defaultdict 

tc = int(input())

for _ in range(tc):
    word = input()
    k = int(input())
    
    alphabet_dict = defaultdict(list)
    
    for i, w in enumerate(word):
        alphabet_dict[w].append(i)

    min_length = float('inf')
    max_length = -1

    for indices in alphabet_dict.values():
        if len(indices) >= k:
            for i in range(len(indices) - k + 1):
                length = indices[i + k - 1] - indices[i] + 1
                min_length = min(min_length, length)
                max_length = max(max_length, length)

    if max_length == -1:
        print(-1)
    else:
        print(min_length, max_length)

이렇게 할 수 있다.