[문자열/백준] 20437번 : 문자열 게임2

- 문제 : https://www.acmicpc.net/problem/20437

 

문제 이해 

- 각 케이스마다 문자열과 숫자 k가 주어진다. 숫자 k는 부분 문자열에 하나의 문자가 k개 이상은 있어야 한다는 것을 의미한다. 

 

- 처음에 문제가 이해가 안되기도 했지만, 알파벳 종류에 상관없이 그럼 모든 문자에 대해서 모든 부분 문자열에 대해 k개 이상이 있는지 확인해야하는 건가? 싶은 생각이 들었다. 그렇다면 케이스가 너무 많아지고, 복잡해질 것 같았다. 

 

- 그래서 풀이를 확인했는데 브루트포스처럼 하지 않고 1) 각 알파벳의 개수를 구한 다음 2) 그 알파벳의 인덱스를 구한 뒤 3) 인덱스 간의 차이 중 최소값과 최대값을 구하면 된다. 

 

- 정답률이 꽤 높았던 골드5 문제이지만, 아직 문자열은 좀 어려운 것 같다,, 익숙해지기까지 시간이 좀 걸릴 듯 하다.

 

풀이 로직 

- 각 케이스마다 단어 w와 숫자 k를 입력 받는다. 

 

- Counter 라이브러리로 단어에 있는 알파벳의 개수를 count_char_dict 딕셔너리에 저장한다. (예시 : {'a' : 2, 'b' : 0,,,})

 

- check는 정답 확인용, max_answer는 조건을 만족하는 최대 문자열 길이, min_answer는 조건을 만족하는 최소 문자열 길이다.

  check_dict는 특정 문자의 index를 저장하는 딕셔너리이다.

 

- 단어 w를 순차적으로 탐색하면서 각 알파벳의 개수가 k개 미만이면 넘어가고, k개 이상인 경우만 check_dict에 {알파벳 : [인덱스1, 인덱스2,,,,]} 형태로 데이터를 저장한다. 

 

- check_dict를 다 완성했다면 각 item을 탐색하면서 key(알파벳, 문자 1개)가 k개일 때의 문자열 길이의 최대값을 max_answer, 최소값을 min_answer에 저장한다. 

-> 예를들어 value_list는 알파벳 'a'의 위치 값들이다. [1, 3, 5, 10,,] 그런데 연속된 문자열에서 알파벳 'a'가 k개 있어야 하므로 value_list에서 연속된 인덱스가 k개 만큼 필요하다. 그래서 value_list[i + k - 1] - value_list[i]이고, 문자열의 길이이므로 인덱스 차이값에 + 1을 해준다.

for key, value_list in check_dict.items(): # key(알파벳), value_list(인덱스 리스트)
    for i in range(len(value_list) - k + 1):
        max_answer = max(max_answer, value_list[i + k - 1] - value_list[i] + 1)
        min_answer = min(min_answer, value_list[i + k - 1] - value_list[i] + 1)

 

정답 풀이

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

for _ in range(int(input())):
    w = input().rstrip()
    k = int(input())
    
    count_char_dict = Counter(list(w))
    
    check = False
    max_answer = -1
    min_answer = len(w)
    check_dict = {} # 특정 문자열의 index를 저장하는 딕셔너리 
    
    for i in range(len(w)):
        if count_char_dict[w[i]] < k:
            continue
            
        check = True
        check_dict[w[i]] = check_dict.get(w[i], []) + [i]
        
    for key, value_list in check_dict.items(): # 알파벳, 인덱스 리스트 
        for i in range(len(value_list) - k + 1):
            max_answer = max(max_answer, value_list[i + k - 1] - value_list[i] + 1)
            min_answer = min(min_answer, value_list[i + k - 1] - value_list[i] + 1)
            
    if check :
        print(min_answer, max_answer) 
    else:
        print(-1)

 

참고한 블로그 : Python백준-문자열-게임-2