[Python][백준 20437][문자열] 문자열 게임 2 - 컴도리돌이

반응형

---

풀이과정

해당 문제는 시간 초과를 걸리 줄 알았는데,

생각보다 쉽게 해결되어서

허무(?)했던 문제였다.

(원래 시간 초과 4개 걸리고 해결해야 짜릿한데,,🙄🙄)

 

1. 입력받은 w를 enumerate로 인덱스 번호(i), 문자열(str)로 열거하여

dictionary(ww)에 문자열의 인덱스를 삽입해준다.

 

2.  각 알파벳의 인덱스 정보를 담고 있는 ww를 반복문을 다음과 같이 수행한다.

 

3. 해당 알파벳의 인덱스 리스트를 'str_idx_list'라고 설정하였다.

 

4. 해당 리스트의 크기가 k보다 작으면, 

문제에서 주어진 3,4번 조건을 만족하지 못하기 때문에  continue를 시킨다.

 

5. len_list는 k개를 포함하는 문자의 문자열 길이를 담는 리스트이다.

len_list에 str_idx_list [i+k-1] - str_idx_list [i] +1 값을 넣어준다.

 

여기서 강조된 말은

str_idx_list는 해당 문자의 인덱스 정보가 담겨 있기 때문에

0번째부터 k-1번째까지의 길이를 

저장하기 위한 수식이다.

 

6. len_list가 존재하면 해당 리스트에서 min, max 값을 출력한다.

존재하지 않으면 -1 값을 출력한다.

---

풀이 코드

import sys; input = sys.stdin.readline
for _ in range(int(input())) :
  w,k= input().strip(),int(input())
  ww,len_list = {},[]
  for i,str in enumerate(w) :
    if str in ww : ww[str].append(i)
    else : ww[str] = [i]
  for str in ww :
    str_idx_list = ww[str]
    n = len(str_idx_list)
    if n < k : continue
    for i in range(n-k+1) :
      len_ = str_idx_list[i+k-1] - str_idx_list[i] + 1
      len_list.append(len_)
  if len_list : print(min(len_list),max(len_list))
  else : print(-1)