문제 설명

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

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

[제약 사항]

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

[입력]

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

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

[출력]

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

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

입력

3
KOREAKOREAKOREAKOREAKOREAKOREA
SAMSUNGSAMSUNGSAMSUNGSAMSUNGSA
GALAXYGALAXYGALAXYGALAXYGALAXY

input.txt

출력

#1 5
#2 7
#3 6

output.txt

풀이 과정

문제 자체가 허점이 많아서 욕을 많이 먹은 듯한 문제.
그래서 저도 복잡한 경우는 생각 안 하고 테케 기준으로 잘 통과하도록 작성했습니다.

KOREA나 GALAXY가 패턴인 경우에는 문자를 하나씩 보면서 패턴으로 추가하고, 패턴의 첫 번째 문자와 일치하는 문자가 등장하면 거기까지가 패턴이라고 판단하고 길이를 출력하면 됩니다.

그러나 이는 SAMSUNG이 패턴인 경우에는 제대로 동작하지 않을 겁니다. pattern = [’S’, ‘A’, ‘M’] 이고 현재 보고 있는 값이 인풋의 4번째에 위치한 문자 ‘S’라면 패턴의 첫 번째 문자와는 일치하지만 패턴의 두 번째 글자는 ‘A’이고 인풋의 5번째에 위치한 문자는 ‘U’이기 때문입니다.

그러면 패턴의 전체 값이 한 번이라도 인풋에서 끝까지 등장하는지를 확인해야 합니다. 1번만 찾으면 그때에 여태까지 누적된 pattern의 값이 진짜 패턴임을 확신할 수 있습니다.

주어진 문자열에는 무조건 반복되는 패턴이 있음을 보장하고 풀었습니다.

정답 코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    string = list(input())
    pattern = [string[0]] # 첫 글자는 패턴에 넣어두고 시작
		
    # 패턴의 글자를 가리키는 포인터
    pattern_pointer = 0
    # 패턴과 같은 문자열인지 확인하기 위한 임시공간 - 패턴과 다르면 패턴에 추가됨
    temp = []
		
    # 두번째 문자부터 마지막 문자를 확인할 때까지 반복
    for i in range(1, len(string)):
        # 현재 문자가 패턴 포인터가 가리키는 패턴 문자와 다르다면
        if string[i] != pattern[pattern_pointer]:
            # 패턴 포인터가 0이면 (= 이전에 패턴과 같은 문자를 찾은 적 없음)
            if pattern_pointer == 0:
                # 패턴 중 일부로 판단하여 패턴에 추가
                pattern.append(string[i])
            # 패턴 포인터가 0이 아니면 (= 이전에 패턴과 일부 일치하는 문자를 찾은 적 있음)
            else:
                # 앞서 패턴과 앞부분이 일치했지만 현재 다르기 때문에
                # 결국 아직 패턴이 끝나지 않은 것 -> temp + string[i]를 패턴으로 추가
                pattern += (temp + [string[i]])
                # 패턴 포인터와 임시공간을 초기화
                pattern_pointer = 0
                temp = []
        # 현재 문자가 패턴 포인터가 가리키는 패턴 문자가 같다면
        else:
            # 오 이거 패턴과 일치하는 건가?
            # 뒤를 더 봐야 하기 때문에 일단 임시공간에 추가
            temp.append(string[i])
            # 패턴 포인터 +1 (-> 뒤의 문자와 같은지를 봐야 하니까)
            pattern_pointer += 1
        # 임시공간에 쌓아온 문자열이 패턴의 길이와 일치하면
        if len(temp) == len(pattern):
            # pattern의 값이 반복되는 진짜 패턴임을 확신할 수 있게 됨 -> 더 볼 필요 없으니 반복문 종료
            break
		        
    # 패턴의 길이를 출력
    print("#%d %d" % (test_case, len(pattern)))

이렇게 패턴 포인터가 가리키는 pattern 문자와 string에서 현재 보고 있는 문자가 다르면 이는 패턴에 포함되는 값이기 때문에 패턴에 추가했고, 같다면 임시공간 temp에 넣어두고 패턴 포인터를 한칸씩 이동하며 지금까지 누적된 pattern과 temp의 값이 같은지를 확인합니다.

누적된 temp 길이와 누적된 pattern의 길이가 같다면 pattern의 값이 반복된다는 것이 확인됐기 때문에 반복문을 종료합니다.

이상입니다.

LIST