(Python/🥇5)백준알고리즘 20437번:문자열 게임 2

문제 바로가기 

문자열 게임 2

 

문제:

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

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

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

입력:

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100) 다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000)

 

출력:

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다. 만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

 

 

풀이:

import collections   
import sys  


sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


t = int(input())

# 각각의 테스트 케이스
for i in range(t):
    W = input()
    K = int(input())

    # defaultdict 'alpha'를 생성하여 문자 인덱스의 목록을 저장.
    alpha = collections.defaultdict(list)

	# 단어 'W'의 문자를 하나씩 확인.
    for i in range(len(W)):
        # 현재 문자가 'W' 안에서 최소 'K'번 이상 나타나는지 확인
        # 최소 'K'번 이상 나타나면 해당 문자의 인덱스를 해당 문자에 연결된 목록에 추가
        # defaultdict 을 list로 선언했기때문에 각 key에 list 형식으로 append 가능
        if W.count(W[i]) >= K:
            alpha[W[i]].append(i)

    # 최솟값과 최댓값을 저장할 변수를 초기화
    min_res = 10001
    max_res = -1

    for i in alpha.values():
        # 'K'번 이상 나타나는 문자열의 인덱스 목록을 순회.
        for j in range(len(i) - K + 1):
            # 'K'번 이상 나타나는 부분 문자열의 길이를 계산.
            res = i[j + K - 1] - i[j] + 1

            # 현재까지 발견한 최소 길이를 업데이트.
            min_res = min(min_res, res)

            # 현재까지 발견한 최대 길이를 업데이트.
            max_res = max(max_res, res)

    # 어떤 문자도 없는 경우.
    if not alpha:
        print(-1)  # -1을 출력합니다.
    else:
        print(min_res, max_res)

 

푸는데 오래 걸렸다. 처음에 포문 3개나 썼는데 당연히 안된다.. 또 4번 설명을 잘 못 읽어 올바른 정답을 내지 못했다.

문자열게임 1 풀러 가본다.