[백준 20437] 문자열 게임 2

문제 출처 : https://www.acmicpc.net/problem/20437

 

문제 이해하기

1. 문자의 개수 파악하기

양의 정수 K로 문자열의 길이를 찾는 문제 입니다. 문자는 소문자로 이루어져 있기 때문에 a부터 z까지 총 26개의 문자에 대해 확인을 해야겠지만 K개 이하의 문자는 확인을 하지 않아도 됩니다. 첫 번째 예제의 문자열로 확인을 해보겠습니다.

superaquatornado, K = 2

위 문자에 대해 K는 2이기 때문에 2개이상 존재하지 않는 문자는 신경 쓰지 않아도 됩니다. 그럼 먼저 각 문자가 몇 개씩 존재 하는지 부터 확인해 보겠습니다.

s	u	p	e	r	a	q	t	o	n	d
1	2	1	1	2	3	1	1	2	1	1

K가 2이기 때문에 2개 이하로 존재하는 이들은 확인할 필요가 없습니다. 여기서 확인해야 할 문자는 u, r, a, o만 확인하면 됩니다.

2. 문자열 위치 확인하기

위에서 파악한 u, r, a, o 가 존재하는 위치를 확인합니다. 각 문자가 존재하는 위치로 K개가 들어있는 길이를 구해 가장 짧은 길이와 가장 긴 길이를 찾으면 됩니다. 위 예제로 계속 이해해 보겠습니다.

u	1, 7
r	4, 11
a	5, 8, 13
o	10, 15

각각 u, r, a, o의 위치를 확인해보면 위와 같이 존재합니다. 맨 앞 s가 0번째 위치이기 때문에 u는 1번째 위치와 7번째 위치에 존재합니다. 길이를 확인해 보면 u는 7 - 1 + 1인 7이 u로 시작하고 끝나는 길이가 됩니다. 1을 더하는 이유는 그냥 7에서 1을 빼면 앞의 u가 없는 길이이기 때문 입니다. 실제로 위 예제에서 u로 시작하고 끝나는 값을 확인해보면 uperaqu 로 총 7자라는 것을 알 수 있습니다.

그럼 여기서 의문이 생깁니다. 게임 진행방식의 3번을 보면 어떤 문자 K개를 포함한 가장 짧은 길이를 구하라고 했는데 이렇게 구해도 되는가 입니다. 결론부터 말하자면 어떤 문자 K개를 포함한 가장 짧은 길이는 앞 뒤가 모두 어떤 문자여야 합니다. 그래야 K개의 가장 짧은 문자열이 됩니다.

위 예제에서 a가 2개 포함된 가장 짧은 문자열은 aqua입니다. 앞, 뒤가 모두 a일 때 가장 짧은 문자열임을 알 수 있습니다. 앞, 뒤에 다른 문자가 있다면 a가 2개 포함된 가장 짧은 문자열이 될 수 없습니다.

코드 작성하기

그럼 앞에서 이해한 내용을 바탕으로 코드를 작성해 보겠습니다.

입력 받기

T = int(input())

for _ in range(T):
    W = input()
    K = int(input())

먼저 게임의 수 T를 입력 받습니다. 다음으로 T개의 게임을 for문을 통해 구현하고 각 게임에 사용될 문자열 W와 정수 K를 입력 받습니다.

문자의 개수 확인하기

문자열 W안에 문자열이 몇 개 있는지 확인합니다. a부터 z까지 리스트를 만들어도 되겠지만 간단한 딕셔너리를 통해 문자의 개수를 세도록 하겠습니다.

    cnt_dict = {}

    for c in W:
        cnt_dict[c] = cnt_dict.get(c, 0) + 1

cnt_dict는 각 문자가 몇 개씩 존재하는지 확인하는 딕셔너리 입니다. W의 모든 문자에 대해 몇 개씩 존재하는지 개수를 세어줍니다. 딕셔너리의 get 함수에 대해 잘 모른다면 아래 링크를 통해 get의 사용법에 대해 확인 바랍니다.

https://wikidocs.net/192441#_6

04. 딕셔너리로 만드는 성적 관리 프로그램

해당 문자의 개수를 가져와 1씩 계속 더해주면 각 문자의 개수를 정확하게 구할 수 있습니다.

문자 위치 확인

위에서 구한 문자의 개수를 통해 각 문자들이 어느 위치에 있는지 확인하는 코드를 작성해 보겠습니다.

    chk_dict = {}

    for i, c in enumerate(W):
        if cnt_dict[c] < K:
            continue

        chk_dict[c] = chk_dict.get(c, []) + [i]

chk_dict는 각 문자가 어느 위치에 있는지 확인하는 딕셔너리 입니다. W문자열을 한 번 더 반복합니다. 각 문자열을 확인해서 해당 문자가 K개 미만 이라면 확인할 필요가 없기 때문에 continue 구문을 통해 넘어갑니다.

K개 이상이라면 해당 위치를 저장합니다. get 구문의 사용법과 리스트에 리스트를 더해줄 경우 어떻게 되는지 정확하게 이해해야 합니다.

길이 구하기

이제 앞에서 구한 문자의 위치를 통해 가장 짧은 길이와 가장 긴 길이를 구해보도록 하겠습니다.

    max_ans = -1
    min_ans = len(W)  
    for key, val in chk_dict.items():
        for i in range(len(val) - K + 1):
            val_len = val[i + K - 1] - val[i] + 1
            max_ans = max(max_ans, val_len)
            min_ans = min(min_ans, val_len)

max_ans는 가장 긴 길이를 저장하는 변수 입니다. 초기값을 가장 짧은 길이인 -1로 하였습니다. min_ans는 가장 짧은 길이를 저장하는 변수 입니다. 초기값은 가장 긴 길이인 W의 길이로 하였습니다. 다음으로 chk_dict를 순회하면서 길이를 구해 줍니다.

key에는 해당 문자가 들어 있고, val에는 key의 문자가 위치한 인덱스 정보가 리스트 형태로 저장되어 있습니다. 위의 예제에서 a를 예로 들면 key가 a가 되고 val은 [5, 8, 13]이 됩니다.

각 문자에 대해 val 이라는 리스트롤 통해 max_ans와 min_ans를 갱신해 줍니다. 이 때 바로 다음 인덱스를 확인하는 것이 아니라 K개 만큼 떨어진 인덱스를 확인합니다. 따라서 val_len을 구할 때 K값을 더한 인덱스를 확인하는 것입니다.

결과 출력

계산한 결과를 통해 결과를 출력해 줍니다.

    if chk_dict:
        print(min_ans, max_ans)
    else:
        print(-1)

chk_dict가 존재한다면 결과값이 있다는 뜻입니다. 따라서 chk_dict가 존재하면 min_ans와 max_ans를 출력하고, chk_dict가 존재하지 않는다면 -1을 출력해 줍니다.

전체 코드

전체 코드를 확인해 보겠습니다.

T = int(input())

for _ in range(T):
    W = input()
    K = int(input())
    
    cnt_dict = {}

    for c in W:
        cnt_dict[c] = cnt_dict.get(c, 0) + 1

    chk_dict = {}

    for i, c in enumerate(W):
        if cnt_dict[c] < K:
            continue

        chk_dict[c] = chk_dict.get(c, []) + [i]

    max_ans = -1
    min_ans = len(W)  
    for key, val in chk_dict.items():
        for i in range(len(val) - K + 1):
            val_len = val[i + K - 1] - val[i] + 1
            max_ans = max(max_ans, val_len)
            min_ans = min(min_ans, val_len)
        
    if chk_dict:
        print(min_ans, max_ans)
    else:
        print(-1)