파이썬으로 시퀀스에서 최대 k-반복 부분 문자열 찾는 프로그램 구현하기

문제 이해하기

문자 시퀀스 s가 주어졌을 때, 문자열 w를 k번 이어 붙인 결과가 s의 부분 문자열이 된다면 w를 'k-반복(k-repeating) 문자열'이라고 정의합니다. 이때 w의 최대 k-반복 값은 w가 s 안에서 반복될 수 있는 가장 큰 k를 의미합니다. 만약 w가 s의 부분 문자열이 아니라면 최대 k-반복 값은 0이 됩니다.

예를 들어 s = "papaya", w = "pa"라고 가정해 보겠습니다. "pa"가 "papaya" 안에 두 번 포함되어 있으므로 출력 결과는 2가 됩니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 먼저 파이썬 내장 메서드 count()를 사용해 s 안에 w가 등장하는 횟수(Count)를 구합니다.
• Count가 0이라면 w가 s에 존재하지 않는 것이므로 0을 반환합니다.
• Count부터 1까지 1씩 감소시키면서 반복하고, w를 i번 반복한 문자열(w*i)이 s에 존재하는지 확인합니다.
• 조건을 만족하는 가장 큰 i를 발견하는 즉시 해당 값을 반환합니다. 큰 값부터 검사하기 때문에 첫 번째로 조건을 만족하는 값이 곧 최대 k-반복 값입니다.

파이썬 구현 예제

다음 코드를 통해 실제 동작 방식을 더 잘 이해할 수 있습니다.

def solve(s, w):
    Count = s.count(w)
    if Count == 0:
        return 0
    for i in range(Count, 0, -1):
        if w * i in s:
            return i

s = "papaya"
w = "pa"
print(solve(s, w))

입력

"papaya", "pa"

출력

2

동작 원리 살펴보기

위 코드에서 s.count(w)는 겹치지 않는 w의 등장 횟수를 반환하므로, 가능한 최대 반복 횟수의 상한선 역할을 합니다. 이후 w * i 연산은 파이썬의 문자열 반복 기능을 활용해 w를 i번 이어 붙인 문자열을 생성하고, in 연산자로 해당 문자열이 s에 포함되어 있는지 검사합니다. 상한값부터 내림차순으로 탐색하기 때문에 효율적으로 최대 k-반복 값을 찾을 수 있습니다.