[BOJ] 백준 1305번 광고 Python

문제

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

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

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

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

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

입력

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

출력

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

제한

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

5
aaaaa

예제 출력

1

 

풀이

문제의 이해에는 큰 어려움은 없다. 전광판에는 문자의 마지막에 다시 문자의 처음이 붙어 출력된다. 이때 원본 문자열이 될 수 있는 문자 중 가장 짧은 것의 길이를 출력하면 된다.예제의 원본 문자가 a이면 길이 5의 전광판에 aaaaa가 출력될 수 있으므로 답은 1이다.

 

전광판에 나타나는 전체 문자의 길이에서 그 문자의 공통된 접두사와 접미사의 길이를 뺀 것이 원본 문자의 길이가 된다. 왜냐하면 접두사와 접미사가 같다는 것은 문자가 처음부터 다시 시작한 것으로 보아도 되기 때문이다.

결국 전광판에 나타나는 문자의 길이 - 공통되는 접두(미)사의 최대 길이를 빼면 원본 문자의 최소 길이를 구할 수 있다.

 

 

조금 더 상세히 설명하면...

원본 문자가 끝난 뒤 다시 시작되기 때문에 현재 전광판에 보이는 문자는 "원본문자 + 원본 문자의 앞부분" 일 것이다.

하지만 세준이가 랜덤한 시점에 전광판을 보기 때문에 전광판에 보이는 문자는 "원본 문자의 뒷부분 + 원본문자 + 원본 문자의 앞부분"이 될 수도 있다.

또는 원본 문자의 길이가 전광판에 나타날 수 있는 문자의 길이의 반 보다 훨씬 짧으면 "원본문자의 뒷 부분 + 원본 문자 + ... + 원본 문자 + 원본 문자의 앞부분" 또한 될 수 있다.

하지만 원본문자가 중간에 몇 번 반복되든 그건 모두 접두사와 접미사가 공통되는 부분일 것이다.

따라서 원본 문자가 전광판 안에서 몇 번 반복되든 신경 쓸 필요는 없다. 결국 접두사와 접미사가 공통되는 가장 긴 부분문자열의 길이만 구하면 된다.

L = int(input())
string = input()

def get_lps_of_full_string(string , L):
    lps = [0] * L
    prefix_length = 0
    pointer = 1
    while pointer < L:
        if string[prefix_length] == string[pointer]:
            prefix_length += 1
            pointer += 1
        else:
            if prefix_length != 0:
                lps[pointer-1] = prefix_length
                prefix_length = lps[prefix_length - 1]
            else:
                pointer += 1
    return prefix_length


print(L - get_lps_of_full_string(string, L))

만약 KMP알고리즘을 알고 있다면 굳이 설명이 필요없을 것이다.

위의 코드에서 prefix_length는 문자열에서 접두사인 동시에 접미사가 될 수 있는 가장 긴 문자열의 길이를 의미한다.
처음부터 pointer가 가리키는 부분까지 접두사와 접미사가 가장 긴 부분을 찾는 함수이다.

이 전광판에서 모든 문자열을 다 확인 하였을 때, 공통되는 접두사와 접미사의 길이를 구하여야 하기 때문에, 무조건 마지막에 나오는 prefix_length를 출력해야 한다. 중간에 더 긴 prefix_length가 있다고 해도 정답과는 관련이 없다.

다른 풀이

def get_lps_of_full_string(string, L):
    lps = [0] * L
    prefix_length = 0
    for i in range(1, L):
        while prefix_length > 0 and string[i] != string[prefix_length]:
            prefix_length = lps[prefix_length - 1]
        if string[i] == string[prefix_length]:
            prefix_length += 1
            lps[i] = prefix_length
    return prefix_length

다른 부분은 동일하다.

이 풀이가 조금 더 느린데 이유는 잘 모르겠다.

정확하지는 않지만 아마 while prefix_length > 0 and string[i] != string[prefix_length]에서 조건을 검사하는 곳에서 시간이 조금 더 소요되는 것 같다.

이 코드도 백준 1등 먹었다.

pypy도 같이 검색하면 1등이 아니다.
pypy로는 굳이 제출 안해보았다.

백준 1등 자랑하기