난이도

Gold 5

풀이 참고 유무

?

막힌 부분

시간 초과

문제

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

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

입력

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

출력

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

예제 입력

2
superaquatornado
2
abcdefghijklmnopqrstuvwxyz
5

예제 출력

1
abaaaba
3

문제 검토

문자열을 완탐하게 되면 쉽게 답을 구할 수 있을 것 같지만 n2의 수행시간으로 완탐하며 t번 반복하기에는 10,000이라는 범위는 꽤 넓다.

자료구조를 잘 사용해서 시간 초과가 나지 않게 문제를 해결하자.

풀이(python)

Python - 시간초과

t=int(input())    
for x in range(t):
    s=input()
    k=int(input())
    shortans=99999
    longans=-1
    anschk=False
    check=False  
    for y in range(len(s)):
        cnt=0
        scnt=0
        for z in range(y,len(s)):    
            cnt+=1
            if s[y]==s[z]:
                scnt+=1
            if scnt==k:
                check=True
                anschk=True
                break
        if check:
            shortans=min(shortans,cnt)
            longans=max(longans,cnt)
            check=False
    check=False
    if not anschk:
        print(-1)        
    else:
        print(shortans,end=' ')
        print(longans)

모든 테스트 케이스를 통과하고 로직에 문제가 없는 것 같지만 n2의 시간을 사용하기 때문에 시간 초과가 났다.

Python - 정석풀이 - 해쉬맵(dictonary) 사용

# dict에 key 값이 없어도 원하는 값을 append 할 수 있음
from collections import defaultdict            
t=int(input())    
for x in range(t):
    s=input()
    k=int(input())
    alpha=defaultdict(list)
    #문자가 k개 이상인 문자들을 key로 하고 그에 맞는 인덱스번호를 value로 append
    for y in range(len(s)):
        if s.count(s[y])>=k:
            alpha[s[y]].append(y)
    #k개가 되는 문자가 없다면 -1
    if not alpha:
        print(-1)
        continue        
    minans=999999
    maxans=0
    #딕셔너리의 value인 리스트를 대상으로 문자열 게임 시작
    for y in alpha.values():
        #문자개수를 k에 맞춰서 끝에서 처음을 빼는 방식으로 길이 계산 후 최소와 최대 길이를 구함
        for z in range(len(y)-k+1):
            minans=min(y[z+k-1]-y[z]+1,minans)
            maxans=max(y[z+k-1]-y[z]+1,maxans)            
    print(minans,maxans)

defaultdict이라고 하는 자료구조를 사용했다.
dictonary의 서브 클래스이고 해당 딕셔너리의 요소들의 자료형을 default로 지정할 수 있다는 장점이 있다.
만약 value를 정하지 않고 key값만 지정해주면 int면 default로 0 list면 default로 [] 이 value로 들어간다.

문제에서 구하는 것은 일단 k개의 같은 문자가 필요하고 k로 양 쪽이 끝나는 문자열의 길이를 원하고 있다.

짧은 문자열은 양 쪽이 k에 해당하는 문자로 끝나라는 조건은 없지만 k개를 정확히 포함하면서 가장 짧기 위해서는 무조건 양 쪽이 k에 해당하는 문자로 끝나야 한다.

그런 이유로 먼저 dictonary에 담겨 있는 알파벳 별 인덱스를 k개 만큼 잘라서 끝과 처음을 뺀 후 길이를 계산해서 가장 짧고 긴 문자열의 길이를 각각 구한다.

걸린 시간

36:12 - (시간초과 풀이 기준)

총평

defaultdick이라는 좋은 자료구조를 하나 알게 되었다.
데이터 양을 보고 완탐을 생각하면 안됐는데 완탐으로 구현한 것이 독이 되었다.

완탐으로 하지 못한다면 자료구조를 잘 사용하여 좋은 코드를 짜야한다.
한번에 반복으로 원하는 값들의 위치나 정보를 잘 담아둘 수 있는 해쉬맵도 잘 사용해보도록 하자.