SWEA 2007 패턴 마디의 길이 (핵심 : startswith)

💡문제 분석 요약

• 주어진 문자열에 대해서 반복되는 패턴의 길이를 출력한다.
• 문자열은 30글자가 주어지고, 패턴은 최대 10글자이다.

💡알고리즘 설계

• 한글자씩 슬라이싱 하면서 슬라이싱된 패턴이 반복되는지 확인한다.
• 이때 "반복된다"라는 것은 이어붙였을 때, 이게 들어있는지 확인하면 된다.
• 예를들어 sam이 패턴이 되려면 samsamsam이렇게 되어야하는거지, sam1sam2sam3 이건 패턴이 아니다.

💡코드

T = int(input())

for t in range(T):
    lst = input() # 문자열 길이는 30 고정

    for i in range(1, 11): # 1부터 10까지 마디 잘라봄 (마디 최대 길이가 10)
        pattern = lst[:i] # 이 패턴이 "연속으로" 반복되느냐? 를 봐야함.
        if lst.startswith(pattern * (30 // i)): # startswith : 문자열이 특정 패턴으로 시작하는가 ?
            print(f"#{t + 1} {i}")
            break

        """ 아래 코드 안되는 이유 : 문자열 lst가 꼭 패턴만큼 주어지는게 아님.
        KoreaKo 처럼 패턴은 5글자인데 lst가 7글자 주어질 수 있음.
        그래서 패턴을 n배 했을 때 안될수도 있는 것."""
        # if lst == pattern * (30 // i): # 즉, 패턴 연속으로 이어붙였을 때 원래의 문자열이 되느냐 ?
        #     break

💡시간복잡도

• 슬라이싱 : i개 슬라이싱할 때 O(i)인데 최대 10개만 슬라이싱 하므로 O(1)
• for문도 10번만 반복됨.
• 따라서 전체 O(1)만에 끝난다.

💡 틀린 이유, 수정

• SamsungSamsungSamsungSamsungSa 이런식으로 문자열은 30글자인데 패턴이 7자라면, N배가 되지 않는다. 그니까 pattern * N이 문자열과 같지 않을 수 있다는 것이다. 그래서 위 코드에 주석 처리한 것 처럼, 단순히 N배만 비교하면 안되고, 이 패턴으로 start하느냐를 봐야하므로 startswith 메소드를 사용하였다.

💡 느낀점 or 기억할정보

• 문제를 분석하며 꼼꼼히 읽는 게 중요하다.