[Python][백준] 20437. 문자열 게임 2 / 문자열 (G5)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):    
    lst = list(map(str,input().strip()))
    K = int(input())
    dict = {}

    for s in set(lst):
        dict[s] = []
    
    for i in range(len(lst)):
        dict[lst[i]].append(i)
    
    mx,mn = -1, len(lst)+1 

    for d in dict.values():
        if len(d) >= K :             
            for i in range(len(d)-K+1):
                mn = min(mn,d[i+K-1 ] - d[i] + 1)
                mx = max(mx,d[i+K-1 ] - d[i] + 1)
    
    if mn == -1 or mx == -1 : 
        print(-1)
    else : print(mn,mx)

 

 

1. 해당 문제에서 사용되는 알고리즘은 슬라이딩 윈도우이지만,

나의 코드는 딕셔너리를 이용해서 풀었다.

 

2. 우선 문자열을 리스트 형태로 입력받는다.

 

3. 해당 문자열 리스트로 집합으로 만들어 반복문을 돌린다.

각각의 집합들은 딕셔너리의 key값이 된다.

 

4. 문자열 리스트를 반복문으로 돌리고,

각각의 문자들은 key값이 되고 i는 그 문자의 위치가 된다.

해당 값을 이용해서 dict[key].append(i) 의 형식으로 넣어준다.

 

5. mx와 mn의 초기값을 설정해둔다.

 

6. 만들어진 딕셔너리의 values값들을 반복문 돌리고,

value의 길이가 K개 이상인 경우에만 mn, mx와 값을 비교한다.

(아래 반복문은  반복 횟수를 생각하면 된다.)

 

7. mn 또는 mx 하나만 없어도 -1을 출력하니 if문으로 조건을 설정한다.

 

📌 문제 코멘트 

이렇게 많은 수열들을 모두 리스트에 넣으면 메모리 초과가 발생한다.

 

이를 위해 집합 자료 구조를 사용한다.

그리고 N의 범위가 10만이므로 1개의 반복문을 써야한다. 

 

---

📚문제

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

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