백준 1305: 광고 (Python)

문제

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

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

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

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

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

해설

KMP 알고리즘을 응용해 풀 수 있는 문제다. KMP 알고리즘은 접두사(postfix)와 접미사(prefix)에 같은 부분이 있으면, 그 정보를 '부분 일치 테이블'(PI) 에 미리 기록해두었다가 다음 탐색 시 활용한다.

예를 들어, 'ABCAB' 라는 문자열의 PI 테이블은 다음과 같이 구할 수 있다.

 

문자열	A	B	B	A	B
PI TABLE	0	0	0	1	2

 

이 문제에서 주목해야 할 점은 전광판이 문자열을 출력하고, 남는 공간은 다시 이어서 그 문자열을 다시 출력한다는 것이다. 다르게 말하면, 이어서 출력이 된다면 시작과 끝이 같은 부분이 존재한다는 것이다.

 

그러면 '끝 부분을 제외해버리고 남는 부분'이 가능한 광고 문자열이 된다.

문제에서 요구하는 '가능한 가장 짧은 광고 문자열'을 구하려면, 시작과 끝의 중복되는 부분을 최대한 잘라내면 된다.

얼마만큼 잘라내야 할지에 대한 정보는 고맙게도 PI TABLE에 담겨있다.

 

위 예제 테이블을 기준으로 보면, 시작과 끝이 같은 부분은 'AB' 이다.

PI[5] 값인 2만큼 끝 부분을 잘라내주었다.

문자열	A	B	B	A	B
PI TABLE	0	0	0	1	2

 

그러면 제외되고 남은 'ABB' 가 현재 전광판에서 '가능한 가장 짧은 광고 문자열' 이라는 사실을 알 수 있다. 

그러므로 정답은 'ABB'의 길이인 3이 된다.

 

어? 전광판이 옆으로 흘러간다는 조건이 있는데 답을 단정지을 수 있나?

 

라고 생각할 수 있다. 전광판이 흘러가더라도 문제는 없다.

우리는 가능한 가장 짧은 광고 문자열의 '길이' 만 구해주면 된다. 이 경우에도 답은 변함이 없다.

 

위 예제와 같은 상황에서 전광판이 한칸 왼쪽으로 흘러갔다고 생각해보자.

문자열	B	B	A	B	B
PI TABLE	0	1	0	1	2

 

그러면 위와 같이 문자열과 PI TABLE이 바뀔 것이다.

같은 방법으로 '가능한 가장 짧은 광고 문자열' 을 구해보면, 'BB'를 제외하고 남은 'BBA'가 '가능한 가장 짧은 광고 문자열' 이다. 

 

어라? 아까 구했던 'ABB' 문자열이 한칸 옆으로 흘러 'BBA' 가 된 것 같지 않은가?

이런 방식으로 문자열을 구하더라도 가능한 문자열의 길이는 변하지 않는다.

그러므로 우리는 여전히 답이 3이라고 이야기할 수 있다.

코드

def createTable(pattern):
    table = [0] * N
    i = 0
    for j in range(1, N):
        while i > 0 and pattern[i] != pattern[j]:
            i = table[i-1]
        if pattern[i] == pattern[j]:
            i += 1
            table[j] = i
    return table


L = int(input())
plain_text = input()
N = len(plain_text)
res = createTable(plain_text)
print(N-res[N-1])

 

여담

 

'끝났다는 것은 다시 시작된다는 것을'.. KMP 알고리즘의 원리가 생각나는 제목이다.

노래가 좋으니 들어보도록 하자 ^0^