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

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

20437번: 문자열 게임 2

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:34:42

 

---

 

문제 설명

 

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

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을 출력한다.

 

입력 예시

 

2
superaquatornado
2
abcdefghijklmnopqrstuvwxyz
5

 

출력 예시

 

4 8
-1

 

 

---

 

풀이

 

프로젝트 막바지라 거기에 온 힘을 쏟다 보니, 참으로 오랫만에 포스팅하는 기분이 든다...

 

단순히 길이 K부터 len(W)까지 모든 문자열을 조사하게 되면 반드시 시간초과를 맞닥뜨리게 된다.

자, 그럼 발상을 전환해 볼 때다.

 

3번의 조건을 잘 생각해보면, 어떤 문자를 정확히 K개 포함하는 가장 짧은 연속 문자열은 그 문자가 시작과 끝에 위치하는 상황을 만족한다. 그래야만 첫 번째 문자가 시작에, 마지막 문자가 끝에 정확히 위치함으로써 가장 짧다는 조건을 만족하기 때문이다. 즉 본질적으로 4번 문제를 풀이함과 동시에 가장 긴 문자열과 가장 짧은 문자열을 구하는 상황과 동일하다.

 

우리는 여기에서부터 출발해볼 수 있을 것 같다. 문자열이 기껏해야 알파벳 소문자로 이루어져 있으므로, 문자열을 한 번 순회하며 각 문자열 종류의 인덱스를 저장해볼 수 있다. 이 한번의 순회로 우리는 다음 정보를 얻는다.

 

• 각 알파벳 소문자의 총 문자 등장 횟수와 (소문자 인덱스 리스트의 길이)
• 그 문자들의 등장 위치 (소문자 인덱스 리스트의 각 원소값)

 

만약 이 인덱스 리스트가 K보다 크거나 같다면, 이 인덱스 리스트를 순회하며 3번 혹은 4번의 조건이 되는(첫 번째 글자와 마지막 글자가 해당 문자로 같고, 총 K개의 원소를 포함하는) 경우의 수를 슬라이딩 윈도우로 구할 수 있다.

 

 

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline

def find_string(K, W) :
  minval, maxval = len(W)+1, -1
  alphabet_dict = defaultdict(list)
  for i in range(len(W)) :
    alphabet_dict[W[i]].append(i)

  for idx_list in alphabet_dict.values() :
    if len(idx_list) < K :
      continue
    for i in range(len(idx_list)-K+1) :
      minval = min(minval, idx_list[i+K-1] - idx_list[i] + 1)
      maxval = max(maxval, idx_list[i+K-1] - idx_list[i] + 1)
  return minval, maxval

T = int(input())
for _ in range(T) :
  W = input().strip()
  K = int(input())
  minval, maxval = find_string(K, W)
  if maxval == -1 :
    print(maxval)
  else :
    print(minval, maxval)

풀이 완료!