[SWEA/2007/파이썬3(python3)] 패턴 마디의 길이

[SWEA/2007/파이썬3(python3)] 패턴 마디의 길이

문제

패턴에서 반복되는 부분을 마디라고 부른다. 문자열을 입력 받아 마디의 길이를 출력하는 프로그램을 작성하라.

제한사항

• 각 문자열의 길이는 30이다. 마디의 최대 길이는 10이다.

입력

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 길이가 30인 문자열이 주어진다.

3
KOREAKOREAKOREAKOREAKOREAKOREA
SAMSUNGSAMSUNGSAMSUNGSAMSUNGSA
GALAXYGALAXYGALAXYGALAXYGALAXY

출력

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

#1 5
#2 7
#3 6

풀이

case_count = int(input())

for i in range(1, case_count + 1):
    string = input()
    word = ''
    for char in string:
        word += char
        length = len(word)
        if word == string[length:length+length]:
            break
    print('#{} {}'.format(i, len(word)))

설명

또 설명을 대충 읽는다는 안좋은 버릇을 버리지 못하고 풀었는데 뭔가 잘못된 풀이임에도 불구하고 정답처리가 된 데다가 오히려 괜찮아보이는 코드가 나와서 기념으로 기록해두려 한다. 일단 다른 사람들의 풀이방식은 이렇다. 주어지는 각 문자열의 길이는 30이고 마디의 최대 길이는 10이니 마디의 최대길이인 10까지의 단어를 추적한 뒤에 남은 문자열들이 이 단어의 반복인지 검사하는 형태이다. 나는 이 10자라는 제약조건을 또 그냥 띄엄띄엄보고 넘겨서... 마디도, 문자열도 그 길이에 제한이 없다고 가정하여 코드를 짰다. 또 안좋은 버릇이 나온 것이다.

 

최대길이가 정해지지 않은 패턴을 어떻게 문자열에서 찾을 수 있을까 고민해봤는데 같은 길이의 문자열을 계속해서 추적해나갔을 때 일치하는 단어가 오는 순간이 바로 이 단어가 패턴이라는 것이 판명 되는 부분이다. 예를 들어 첫번째 예제인 KOREA로 예를 들어보자.

 

1. 패턴이 1글자일 경우 조사할 단어가 K이고 그 뒤에 바로 O가 와서 패턴이 아니다.
2. 패턴이 2글자일 경우 조사할 단어가 KO이고 그 뒤에 RE가 와서 패턴이 아니다.
3. ......
4. 패턴이 5글자일 경우 조사할 단어가 KOREA이고 그 뒤에 KOREA가 와서 두 개가 일치하므로 패턴은 KOREA이다.

 

그렇게 5를 리턴한다. 는 식으로 코드를 짰고 정답처리가 됐지만 이건 틀린 알고리즘이다. 왜냐. 알파벳이 반복되는 단어가 있다면 쉽게 무너지는 알고리즘이기 때문이다. 예를 들어 MMORPG라는 패턴으로 입력값이 들어왔다면 논리상 6이 리턴돼야 맞지만 위 코드로는 1이 리턴된다. 문제는 저 코드가 정답처리된다는 것이다. 그래서 수정한 것이 아래의 코드이다.

 

for i in range(1, case_count + 1):
    string = input()
    word = ''
    for char in string:
        word += char
        length = len(word)
        if word == string[length:length+length]:
            rest_string = string[length:]
            rest_string = rest_string.replace(word, '')
            if len(rest_string) < len(word):
                break
    print('#{} {}'.format(i, len(word)))

위에서 말했던 과정을 통해 패턴을 찾았다고 판단됐을 때 그 패턴을 문자열에서 전부 지워버리면 아무리 글자가 많이 남아도 패턴만큼의 글자가 남지 않아야 올바른 패턴이라고 할 수 있다. 두번째 예제인 SAMSUNGSAMSUNGSAMSUNGSAMSUNGSA에서 확인해볼 수 있듯이 SAMSUNG이라는 글자를 전부 지워도 SA라는 자투리가 남는다는 것을 확인할 수 있다. 이런식으로 하면 KKKKKAAAAAKKKKKAAAAAKKKKKAAAAA나 MMORPGMMORPGMMORPGMMORPGMMORPG라는 예제에 대해서도 정확한 패턴의 길이인 10과 6을 반환한다는 것을 확인해볼 수 있다. 물~론 이 코드도 헛점이 있는데 ABCDEFGHUJKLMNOPQRSTUVWXYZWLWM같이 패턴이 없는 문자열을 넣으면 넣은 문자열의 길이인 30이 그대로 반환되는 것, 2번째 예제였던 SAMSUNGSAMSUNGSAMSUNGSAMSUNGSA에서 맨 뒷글자인 SA를 ZX로 바꿔도 패턴 그대로로 인식한다는 점이다. 뭐 아무튼 문제 자체에도, 설명에도, 정답처리에도 전부 구멍이 숭숭 나있는 허술한 문제다.

 

하지만 오히려 문제 설명이 애매하고 정답처리가 너무 널널해서 오히려 상상력을 자극하는 좋은 문제였다.