1133 반복되지 않는 단어

문제 - 입력 - 출력 풀이 과정 - 문제 이해 및 조건 판별 - K-반복X 문자열 찾기 후기

문제

자세한 문제는 아래의 백준 링크를 참고하자.

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

자연수 K가 주어졌을 때, 문자열 S에 연속해서 K번 나오는 부분 문자열이 없을 때, 그 문자열 S를 K-반복X라고 부른다.
예를 들어, CCABAABAABAC는 4-반복X이다. 하지만, 3-반복X는 아니다. 그 이유는 ABA가 연속해서 3번 반복되기 때문이다. CCABAABACABA와 ABABAABA는 3-반복X인 단어이다.
K, N, 그리고 A가 주어졌을 때, 길이가 N이면서, K-반복X이면서 알파벳 처음 A개로만 이루어진 단어 중 사전 순으로 가장 앞서는 것을 출력하는 프로그램을 작성하시오.

- 입력

첫째 줄에 세 정수 K, N, A가 주어진다.

- 출력

문제의 정답을 출력한다. 만약 그러한 것이 없을 때는 -1을 출력한다.

풀이 과정

- 문제 이해 및 조건 판별

문제의 K-반복X 의 조건을 이해하기 힘들었다.

처음엔 길이가 2 이상인 문자열이 문자열 내에서 K회 이상 등장하는 것을 말하나? 싶었는데, 코드를 작성하여 돌려보다 보니 점점 개념이 이해되었다.

중요한 부분은 K회 이상 연속으로 반복되느냐였고, 다음과 같이 K-반복X인지 확인하는 함수를 작성했다.

checkRepeatX()


def checkRepeatX(string, targetTime):
    for targetLength in range(1, len(string)): # 타겟 문자열의 크기 재기 
        listrepeatedString = []

        for i in range(0, len(string) - targetLength + 1):
            
            repeatString = string[i:i + targetLength]
            if repeatString in listrepeatedString:
                continue
            else:
                listrepeatedString.append(repeatString)

            intEqualCount = 0

            for j in range(0, len(string) - targetLength * targetTime + 1):
                boolEqual = True
                for k in range(targetLength * targetTime):
                    if not string[j + k] == repeatString[k % targetLength]:
                        boolEqual = False
                        break
                
                if boolEqual:
                    return False
                
        
    return True

- K-반복X 문자열 찾기

조건 확인 함수가 잘 작동하는 것을 예제 출력으로 확인하고, K-반복X 문자열을 찾는 코드를 작성했다.

최초 시도


k, n, a = map(int,sys.stdin.readline().strip().split())

setAllowed = tuple(map(lambda x : chr(65 + x), range(0, n)))

listTarget = [0 for i in range(n)]

i = 0

while i < a ** n:
    for j in range(n):
        if listTarget[j] == a:
            listTarget[j] = 0
            listTarget[j + 1] += 1

    if(checkRepeatX(listTarget, k)):
        for char in reversed(listTarget):
            print(setAllowed[char],end='')
        exit()

    i += 1
    listTarget[0] += 1

최초 시도엔 위와 같이 시도하였다.

문자열의 길이만큼 0을 채운 리스트를 생성,

리스트의 첫 번째 인덱스에 1을 더해가며 허용된 문자의 크기를 초과하면 다음 인덱스로 넘겨줌.

의 방법으로 브루트포스를 시도했는데, 당연하지만 무지막지한 시간 소요를 마주하게 되었다.

최초 시도의 풀이에서는,

k, n, a가 3, 20, 2 만 되어도 실 컴퓨터 환경에서 2초정도 소요되었고,

3, 50, 2에서는 영겁의 시간을 기다려도 풀리지 않았다.

머리를 감싸고 고민하다가, 다음과 같은 풀이를 시도했다.

최종 시도


k, n, a = map(int,sys.stdin.readline().strip().split())

tupleAllowed = tuple(map(lambda x : chr(65 + x), range(0, n)))

listTarget = []

i = 0

while len(listTarget) < n:
    listTarget.append(0)
    while(not checkRepeatX(listTarget, k)):
        listTarget[len(listTarget) - 1] += 1

        while(max(listTarget) == a):
            indexMax = listTarget.index(a)
            if indexMax - 1 == -1:
                print(-1)
                exit()
            listTarget[indexMax] = 0
            listTarget[indexMax - 1] += 1

for i in listTarget:
    print(tupleAllowed[i],end='')

해당 풀이는 처음부터 n크기의 리스트를 생성하는 것이 아닌,

공 리스트를 생성

리스트 끝에 0을 추가한다.

리스트가 K-반복X 인지 확인하고, 아니라면 마지막 인덱스의 값을 1 추가한다.

리스트에서 사용된 문자가 허용된 문자를 초과한다면, 리스트를 순회하여 앞의 인덱스로 값을 넘겨준다.

순회 중, 제일 앞의 인덱스가 초과하여 -1의 인덱스를 참조해야 할 경우, K-반복X 문자열을 만들 수 없으므로 -1을 출력하고 종료.

리스트의 길이가 n보다 짧다면 2로 돌아간다.

생성된 문자열 출력

의 순서로 진행하였다.

A로 채워진 문자열에서 시작하는 것이 아닌, 한 자리씩 문자를 생성해 나가는 것의 발상이 매우 어려웠다.

그리고, 최종 시도의 풀이로 통과할 수 있었다!

후기

새벽에 3~4시간을 투자하여 푼 문제이다.

처음으로 푼 플레 문제이기도 한데, 생각보다 할만 하다는 생각이 들어 도전하였고, 실제로도 각오 했던 정도의 노력이 들어갔던 것 같다.

풀이한 지 시간이 지난 상태에서 글을 작성하여 다 적진 못하였지만, 풀이에서 언급한 것 이외에도 시행착오가 있었고, 배워갈 것이 많은 문제라고 생각 든다.