[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1305번 _ 광고

https://www.acmicpc.net/problem/1305

1305번: 광고

[문제]

세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다.

전광판에는 같은 내용의 문구가 무한히 반복되어 나온다. 또, 전광판의 크기는 전광판에서 한번에 보이는 최대 문자수를 나타낸다. 만약 전광판의 크기가 L이라면, 한번에 L개의 문자를 표시할 수 있는 것이다.

광고업자는 최대한의 광고효과를 내기 위해서 길이가 N인 광고를 무한히 붙여서 광고한다.

예를 들어, 광고 업자 백은진이 광고하고 싶은 내용이 aaba 이고, 전광판의 크기가 6이라면 맨 처음에 보이는 내용은 aabaaa 이다. 시간이 1초가 지날 때마다, 문자는 한 칸씩 옆으로 이동한다. 따라서 처음에 aabaaa가 보였으면 그 다음에는 abaaab가 보인다. 그 다음에는 baaaba가 보인다.

세준이가 어느 순간 전광판을 쳐다봤을 때, 그 때 쓰여 있는 문자가 입력으로 주어졌을 때, 가능한 광고의 길이중 가장 짧은 것을 출력하는 프로그램을 작성하시오.

 

[입력]

첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다.

[출력]

첫째 줄에 가능한 광고의 길이중 가장 짧은 것의 길이를 출력한다.

[제한]

• 1 ≤ L ≤ 1,000,000
• 광고판에 보이는 문자열은 알파벳 소문자로만 이루어져 있다.

[아이디어]

1) 맨 앞 글자를 기준으로 접두사와 접미사가 일치하는 순간이 있다면, 접미사를 제외한 부분의 문자열이 2번째 반복되어 접두사 부분까지 보이는 상황이라 생각할 수 있다.

2) 반복되는 문자열이 가장 짧기 위해서는 그 일치하는 접두사가 가장 길어야한다.

3) kmp 알고리즘의 일부를 활용해 가장 긴 일치하는 접두사와 접미사의 길이를 구한다.

4) 문자열의 일부가 아닌 처음부터 끝까지에 대해 접두사와 접미사를 확인하므로, 저장하는 길이 배열의 마지막 원소를 활용한다.

 

# 시간초과
l = int(input())
s = input()
ss = list(s)
i = 1
tmp = ""
while i<l:
    tmp += ss[i-1]
    n = l//i + 1
    if s in tmp*n:
        break
    i+=1
print(i)

어림도 없었다. in 연산 외에도 문자열을 반복적으로 더하는 것과 tmp*n 연산이 아마 시간을 많이 잡아먹을 것이다.

n=int(input())
s=input()
t = [0]*n
j = 0
for i in range(1,n):
    while j>0 and s[i]!=s[j]:
        j = t[j-1]
    if s[i]==s[j]:
        j += 1
        t[i] = j
print(n-t[-1])