[백준] 20437. 문자열 게임 2

 

📌문제

20437번: 문자열 게임 2

 

🎖️난이도

 

✔️풀이

# 정답
import sys
input = sys.stdin.readline
from collections import defaultdict

t = int(input())

for _ in range(t):
    w = input()
    k = int(input())
    answer1, answer2 = 10000, 0 # INF 필요 X. 문제 조건 활용!
    
    if k == 1:
        print(1, 1)
        continue
    
    # k개 이상 있는 문자만 idx들 모두 저장
    overK_idx_dict = defaultdict(list)
    
    for i in range(len(w)):
        if w.count(w[i]) >= k:
            overK_idx_dict[w[i]].append(i)
    # {'u': [1, 7], 'r': [4, 11], 'a': [5, 8, 13], 'o': [10, 15]}

    if not overK_idx_dict:
        print(-1)
        continue
    
    # 여기서 모든 문자 탐색 X! k개 이상 있는 문자(idx)만 게임 진행
    for idx_list in overK_idx_dict.values():
        for i in range(len(idx_list)-k+1): # 'a' : i는 0~1
            tmp_len = idx_list[i+k-1] - idx_list[i] + 1
            answer1 = min(answer1, tmp_len)
            answer2 = max(answer2, tmp_len)
    
    print(answer1, answer2)

 

# 시간초과 (완전탐색)
import sys
input = sys.stdin.readline

t = int(input())
INF = int(1e9)

for _ in range(t):
    w = input()
    k = int(input())
    answer1, answer2 = INF, 0
    
    if k == 1:
        print(1, 1)
        continue
    
    for i in range(len(w)-1):
        for j in range(i+1, len(w)):
            if w[j] == w[i] and w[i:j+1].count(w[i]) == k:
                answer1 = min(answer1, len(w[i:j+1]))
                answer2 = max(answer2, len(w[i:j+1]))
                break
    
    if answer1 == 0 or answer2 == 0:
        print(-1)
        continue
    
    print(answer1, answer2)

 

# 시간초과 (완전탐색)
import sys
input = sys.stdin.readline

t = int(input())
INF = int(1e9)

for _ in range(t):
    w = input()
    k = int(input())
    answer1, answer2 = INF, 0
    
    if k == 1:
        print(1, 1)
        continue
    
    for i in range(len(w)-1): 
        cnt = 1
        for j in range(i+1, len(w)):
            if w[j] == w[i]:
                cnt += 1
                if cnt == k:
                    answer1 = min(answer1, len(w[i:j+1]))
                    answer2 = max(answer2, len(w[i:j+1]))
                    break
    
    if answer1 == INF or answer2 == 0:
        print(-1)
        continue
    
    print(answer1, answer2)

 

🧠노트

처음 접근했던 방식처럼 완전탐색(Brute Force)으로 풀면

count를 쓰든 안쓰든 시간초과..

 

따라서 여기서 포인트는,

2중 for문으로 모든 문자마다 문자열 게임을 돌리는 게 아니라

K개 이상으로 있는 문자에 대해서만 문자열 게임을 돌리는 것!

 

즉, 주어진 문자열에서 K개 이상인 문자(알파벳)와 그 위치(idx)를 기록해둔다.

이때, defaultdict를 이용한다!

from collections import defaultdict
...

# string : "superaquatornado"
# {'u': [1, 7], 'r': [4, 11], 'a': [5, 8, 13], 'o': [10, 15]}

 

이렇게 저장한 후 dict에 저장된 문자 및 인덱스에 대해서만

연속으로 인덱스 K개씩 포함해 길이를 구해주면 된다.

for idx_list in overK_idx_dict.values():
        for i in range(len(idx_list)-k+1): # ex. 'a' : i는 0~1
            tmp_len = idx_list[i+k-1] - idx_list[i] + 1
            answer1 = min(answer1, tmp_len)
            answer2 = max(answer2, tmp_len)

 

🔍참고

-