[백준] 문자열 게임2 : 문자열, 슬라이딩 윈도우

문제

20437번: 문자열 게임 2

핵심 :

1. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
2. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

아이디어

가장 긴 문자열은 문제에서 첫 번째와 마지막 글자가 같아야 한다고 명시가 되어 있다.

사실 가장 짧은 연속 문자열도 마찬가지다.

어떤 문자열에서 알파벳 ‘a’를 3번 포함하는 가장 짧은 문자열을 찾는다고 가정하자.

가장 짧은 문자열은 직관적으로 ‘a’로 시작해서 ‘a’로 끝나야 한다는 것을 알 수 있다.

알파벳 ‘a’도 문자열의 길이에 포함된다.

가장 짧은 문자열을 구할 때 ‘a’가 딱 처음~중간~끝 이렇게 딱 세번만 들어가는 경우가 가장 짧은 문자열이 될 것이다.

따라서 가장 긴 문자열이나 가장 짧은 문자열이나 모두 첫 번째와 마지막 글자가 동일한 문자열이 된다.

풀이

문제 단순화

1. 알파벳 개수 카운팅

   일단 전체 문자열에서 어떤 알파벳을 사용할 수 있는지 알아내야 한다.
   문자열에 포함된 모든 알파벳의 개수를 카운트해서 k개 이상인 알파벳만 사용한다.
   k개 미만 사용된 알파벳은 가장 짧거나 긴 문자열을 만들어 낼 수 없다.

2. 알파벳의 인덱스

   아이디어 에서 이미 양 끝의 알파벳이 동일해야 한다는 정보를 알았기 때문에 k개 이상 사용된 알파벳이 전체 문자열에서 어느 인덱스에서 등장하는지 저장하고 그 인덱스들의 차이를 이용해서 문제를 풀 수 있다.

정리

정확하게 k개를 포함해야 한다.

idxs = 전체 문자열에서 알파벳이 등장하는 위치(index)

idxs에서 k개를 기준으로 idxs의 원소들의 차이를 비교하여 가장 짧은 문자열과 가장 긴 문자열을 찾을 수 있다.

이는 범위를 k로 지정하고 슬라이딩 윈도우 알고리즘으로 풀 수 있다.

나는 단순히 인덱스 차이를 직접 비교하는 과정을 사용해서 문제를 해결했다.

코드

import sys
from collections import defaultdict

In = lambda: sys.stdin.readline().rstrip()
MIS = lambda: map(int, In().split())

T = int(In())
for t in range(T):
   word = In()
   dix = defaultdict(int)
   pos = defaultdict(list)
   for c in range(len(word)):
      dix[word[c]] += 1
      pos[word[c]].append(c)

   K = int(In())
   check = []
   for key, val in dix.items():
      if val >= K:
         check.append(key)

   if len(check) == 0:
      print(-1)
      continue

   ans1 = 10000
   ans2 = 0
   for al in check:  # 26
      ans1 = min(ans1, min(pos[al][i + K - 1] - pos[al][i] + 1 for i in range(len(pos[al]) - K + 1)))
      ans2 = max(ans2, max(pos[al][-i] - pos[al][-(i + K - 1)] + 1 for i in range(1, len(pos[al]) - K + 1 + 1)))
   print(ans1, ans2)