반복되는 스트링을 알아내려면 어떻게 해야 할까요?

조회수 3507회

스트링이 계속 반복되고 있는지 아닌지 확인하는 함수를 만들려고 합니다.

예를 들어

[
    '0045662100456621004566210045662100456621',             # '00456621'반복
    '0072992700729927007299270072992700729927',             # '00729927'반복
    '001443001443001443001443001443001443001443',           # '001443'반복
    '037037037037037037037037037037037037037037037',        # '037'반복
    '047619047619047619047619047619047619047619',           # '047619'반복
    '002457002457002457002457002457002457002457',           # '002457'반복
    '001221001221001221001221001221001221001221',           # '001221'반복
    '001230012300123001230012300123001230012300123',        # '00123'반복
    '0013947001394700139470013947001394700139470013947',    # '0013947'반복
    '001001001001001001001001001001001001001001001001001',  # '001'반복
    '001406469760900140646976090014064697609',              # '0014064697609'반복
]

는 스트링이 계속 반복되면서 나타나는 경우고

[
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

는 그렇지 않은 경우입니다.

엄청 긴 스트링이 들어올 수도 있고, 반복되는 스트링이 엄청 길 수도 있습니다. 제가 쓰고 있는 방법은 처음부터 1개, 2개, 3개, ... 이런 식으로 반복되는 스트링 길이를 점점 늘여가는 방식인데요 이렇게 하니까 너무 느려서 다른 방법이 있는지 알고 싶습니다.

전체 스트링이 반복되고 있는지 아닌지, 반복되고 있다면 반복되는 스트링 중 제일 짧은 스트링이 뭔지 알 수 있을까요?

1 답변

  • 좋아요

    0

    싫어요
    채택 취소하기

    제가 생각하기에 제일 간단하면서 반복을 피하는 방법은 다음과 같습니다

    def principal_period(s):
        i = (s+s).find(s, 1, -1)
        return None if i == -1 else s[:i]
    

    반복되는 구조와 그렇지 않은 구조간의 패턴을 분석해서 코드를 만들었습니다. 패턴은 다음과 같습니다.


    1. 스트링 S의 전체가 반복되는 구조를 가진다면,

    S = ABAB와 같이 표현할 수 있습니다. (단, A,B또한 string)

    임의의 문자 a, b에 대해 A = aA', B = B'b라고 하면 S+S = ABABABAB = aA'BABABAB'b입니다.

    따라서 S가 반복되는 구조를 가진다면 (S+S)[1:-1]A'BABABAB'으로 find(A'BABABAB', S)에서 무조건 원본에서 두 번째 AB가 시작되는 점을 return합니다.



    2. 스트링 S가 반복되는 구조를 가지지 않는다면

    S = AB와 같이 표현할 수 있습니다.(단, A, B는 서로 반복되지 않는 string)

    임의의 문자 a, b에 대해 A = aA', B = B'b라고 하면 S+S = ABAB = aA'BAB'b 입니다.

    따라서 S가 반복되는 구조가 아니라면 (S+S)[1:-1]A'BAB'이고 find(A'BAB', S)는 무조건 None을 return 합니다.

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)