백준 1305 (광고)

문제

---

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

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

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

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

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

 

 

 

 

풀이

---

 

이 문제는 KMP 알고리즘에서 Pi 배열이 형성되는 과정과 Pi 배열을 이해해야 풀 수 있는 문제다.

Pi 는 현재 단어에서 공통되는 문자가 어디까지나오는지 얼마나 나오는지를 파악하기 위한 알고리즘이다.

 

abcabca를 예를 들면

0	0	0	1	2	3	4
a	b	c	a	b	c	a

와 같이 나오게 된다.

 

abcabca

abcabca 접두사 abca 와 접미사 abca 이 겹치는 것을 알 수 있다.

 

이렇게 접두사와 겹치는 접미사를 알아내는 방식이 Pi배열이다.

 

저위의 패턴을 보면 문제의 패턴과 유사하다는 것을 알 수 있다.

 

전체문자열 길이 - 겹치는 부분 = 반복패턴의 길이

 

위 수학식이 나온다는 것을 알 수 있다.

 

문제에서 주어진 문자를 보고 예를 더 들어보자면,

 

1)

aaaaa

aaaaa 접두사 aaaa와 접미사 aaaa가 겹친다.

Pi 를 구하는 알고리즘의 특성상 모든 문자가 겹치는 것은 생각하지 않는다.

 

2)

aabaaa

aabaaa 접두사 aa 와 접미사 aa 가 겹친다.

접미사 aa 를 제거하면 반복되는 패턴 aaba가 나온다.

 

마지막으로 하나의 예만 더 들어보도록하겠다.

 

 

3)

aabaaabaaa

aabaaabaaa 접두사 aabaaa 와 접미사 aabaaa가 같다.

접미사를 제거하고 나면 aaba의 패턴이 반복되는 형태인 것을 알 수 있다.

 

이렇게 Pi배열을 통해 반복되는 접미사의 길이를 알아낸 뒤 빼기만 하면 되는 KMP알고리즘을 알고있다면 쉽게 풀 수있는 문제다.

 

 

<전체코드>

import java.io.*;
import java.util.*;

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	static int min = Integer.MAX_VALUE;
	static int L;
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		L = Integer.parseInt(bufferedReader.readLine());
		String ad = bufferedReader.readLine();
		
		int[] pi = getPi(ad);
		
		min = L - pi[L -1];
		for(int i = 0 ; i < L ; i++) {
			System.out.print(pi[i] + " ");
		}
		System.out.println(min);
	}
	
	
	static int[] getPi(String subAd) {
		
		int len = subAd.length();
		int[] table = new int[len];
		
		int j = 0;
		for(int i = 1 ; i < len ; i++) {
			while(j > 0 && subAd.charAt(i) != subAd.charAt(j)) {
				j = table[j - 1];
			}
			
			if(subAd.charAt(j) == subAd.charAt(i)) {
				table[i] = ++j;
			}
		}
		
		return table;
	}
}