문자열 게임 2(백준 20437번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?✓

---

난이도 체감

1. 최상

2. 상✓

3. 중

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

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

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

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

나의 풀이

import sys
from collections import defaultdict

T=int(input())

for _ in range(T):
    w_location=defaultdict(list)
    W=sys.stdin.readline().strip()
    K=int(sys.stdin.readline().strip())
    for i,w in enumerate(W):
        w_location[w].append(i)
    max_length=0
    min_length=10001
    if w_location:
        for w_l in w_location:
            if len(w_location[w_l])<K:
                continue
            for i in range(len(w_location[w_l])-K+1):
                length=w_location[w_l][i+K-1]-w_location[w_l][i]+1
                if length>max_length:
                    max_length=length
                if length<min_length:
                    min_length=length
    if min_length==10001 or max_length==0:
        print(-1)
    else:
        print(min_length,max_length)

• collections의 defaultdict()를 사용하여 문제를 풀었다.
• 각 문자 별로 존재하는 위치 정보를 dictionary에 저장하고, K개 이상이 존재하는 dictionary에 대해서만 길이를 구했다.
  • 짧은 문자열이든, 긴 문자열이든 K개 존재하는 문자가 양 끝에 존재해야 가장 짧거나, 길 수 있다.
• 따라서 K개 이상의 원소를 갖는 w_location[w_l]의 list에서 w_location[w_l][i+K-1]-w_location[w_l][i]+1 를 했을 때, w_l문자가 K개 포함된 문자열의 길이를 알 수 있다. 그 중에서 가장 긴 값을 max_length, 짧은 값을 min_length에 저장한다.

---

• “슬라이드 윈도우 알고리즘”으로 풀어야 한다는 다른 사람의 힌트를 보고 풀려고 시도했는데, 시간 초과가 발생할 것 같아서 풀지 않았다. 그래도 해당 알고리즘을 알아두면 좋을 것 같다. (따지고 보면 사용한 것과 같은지도 모르겠다)

출처 : https://velog.io/@zwon/슬라이딩-윈도우Sliding-Window