[백준] 20437 문자열 게임 2 (파이썬)

골드 Ⅴ

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

20437번: 문자열 게임 2

 

📄 문제

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

 

위와 같은 방식으로 게임을 T회 진행한다.

 

---

💡 아이디어

• 연속된 문자열의 첫 번째와 마지막 글자가 같고 문자열에 해당 글자가 k개 존재해야 한다.
• 완전 탐색으로 문제를 풀이하면 문자열 게임의 수 T는 1 ≤ T ≤ 100이고 문자열 W와 정수 K가 1 ≤ K ≤ |W| ≤ 10,000 이므로 시간초과가 발생한다.
• 따라서, 딕셔너리를 활용하여 문제를 해결할 수 있다.
• 딕셔너리에 각 문자를 key 값으로 각 문자의 위치를 value 값으로 저장한다.
• 딕셔너리에 저장된 각 문자열의 위치에 따라 최대 길이와 최소 길이를 구한다.
• 각 문자가 k개 이상 존재해야 되기 때문에 각 문자열에 저장된 위치가 k개 이상인 문자만 길이 구하는 연산을 수행한다.
• 딕셔너리에 위치값이 순서대로 저장되어 있으므로 k개 이상의 위치를 갖고 있다면  k 개씩 순차적으로 길이 값을 구한다.
• k개로 구분한 위치의 처음 값과 마지막 값을 활용하여 문자열의 길이를 구한다. (길이 = 마지막 위치 - 처음 위치 + 1)
• 이때의 길이를 최댓값, 최솟값과 비교하여 갱신한다.

 

🟩 첫 번째 아이디어 (완전 탐색) - 시간 초과

• 이중 for문을 활용한다.
• 첫 번째 for문에서 탐색을 시작할 위치(i)를 정한다.
• 두 번째 for문에서는 첫 번째 for문에서 정한 위치 이후부터 탐색한다. (j)
• 두 번째 for문을 탐색하면서 시작 문자와 같은 문자가 등장하면 개수를 세어준다. (cnt += 1)
• 시작 문자와 같은 문자일 때, cnt ==  k가 되면 문자열 길이를 구한다.
• 최대, 최소 값을 비교하여 갱신해 준다

 

✅ 두 번째 아이디어 (딕셔너리 활용) - 최종코드 

• 딕셔너리를 활용하여 문제를 풀이한다.
• 딕셔너리에 각 문자를 key 값으로 각 문자의 위치를 value 값으로 저장한다.
• 각 문자가 k개 이상 존재해야 되기 때문에 각 문자열에 저장된 문자의 위치가 k개 이상이면,
• 딕셔너리에 저장된 각 문자열의 위치에 따라 k개 씩 구분하여 길이를 구한다.
• 최대 길이와 최소 길이를 갱신한다.

 

📝 문제 풀이 (Code)

최종 코드 - 딕셔너리 활용

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    w = input()
    k = int(input())

    # 각 단어의 위치 저장
    posi_dic = {}
    for i in range(len(w)):
        if posi_dic.get(w[i]):
            posi_dic[w[i]].append(i)
        else:
            posi_dic[w[i]] = [i]

    minV = 20001
    maxV = 0
	# 위치 배열로 최대, 최소 길이 찾기
    for value in posi_dic.values():
        n = len(value)
        # 해당 문자 K개 이상을 가지고 있으면 길이 찾기
        if n >= k:
            for s in range(n-k+1):
                cnt = value[s+k-1]-value[s]+1
                if minV > cnt:
                    minV = cnt
                if maxV < cnt:
                    maxV = cnt

    if maxV:
        print(minV, maxV)
    else:
        print(-1)

 

처음 코드 - 완전 탐색 (시간 초과)

t = int(input())
for _ in range(t):
    w = input()
    k = int(input())
    n = len(w)
    # 최댓값, 최솟값 저장
    minV = 20001
    maxV = 0
    
    # 문자열이 k 개 이상이어야 하므로 n-k까지 탐색한다.
    for i in range(n-k+1):
    	# 같이 문자열이 몇 개인지 저장
        cnt = 1
        
        # i 이후 문자부터 탐색
        for j in range(i+1, n):
        	# 같은 문자면 cnt += 1
            if w[i] == w[j]:
                cnt += 1
                
            # 처음 문자와 같은 문자가 k개 포함되면 i번째 문자 탐색 종료
            # 최대, 최소 갱신
            if cnt == k:
                minV = min(minV, j - i + 1)
                maxV = max(maxV, j - i + 1)
                break
    if maxV:
        print(minV, maxV)
    else:
        print(-1)