[BOJ] 백준 1305번 광고 (Java)

#1305 광고

난이도 : 플레 4

유형 : 문자열 / KMP

1305번: 광고

▸ 문제

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

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

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

L 크기의 광고판에서 현재 비춰지는 문자열을 보고 최소의 광고 길이를 추측하면 된다. 광고판의 최대 크기는 100만이기 때문에 문자열의 접두사 접미사를 직접 구해줘야한다. KMP의 개념을 알고있다면 굉장히 간단한 문제이다. 

 

예를 들어, L의 크기가 5이고 현재 눈에 비친 광고판의 문자열은 'aabaa'이라고 하자.

 

a

a

b

a

a

 

가능한 최소의 광고 길이를 구하는 문제이기 때문에 광고 문자는 무조건 L이하 임을 알 수 있다. 그렇다면 나올 수 있는 경우의 수는 다음과 같다.

• aabaa
• aaba
• aab
• 따라서, aab가 가능한 광고의 길이 중 가장 짧다는 것을 알 수 있다.

 

위에 예에서 다뤘다시피 현재 비춰지는 광고판의 문자열 접두사 접미사를 구한 후 전체 광고판의 길이(L)에서 접미사의 길이를 빼주면 된다. 그러면 가능한 광고 길이 중 가장 짧은 광고판의 문자열을 구할 수 있다.

 

접두사 접미사를 구하는 로직은 다음과 같다.

static int[]  makeTable(String pattern) {
	int n = pattern.length();
	int[] table = new int[n];
	int idx=0;
	
	for(int i=1; i<n; i++) {
		while(idx>0 && pattern.charAt(i)!=pattern.charAt(idx)) {
			idx = table[idx-1];
		}
		if(pattern.charAt(i) == pattern.charAt(idx)) {
			table[i] = ++idx;
		}
	}
	return table;
	
}

 

설계

1. 현재 비춰지는 광고판의 문자열(p)의 부분 일치 테이블을 구한다. makeTable(String pattern)
   1. for 1~n : pattern 문자열을 순차대로 탐색한다.
   2. idx>0 일치하는 문자가 발생했을 때, 연속적으로 더 일치하지 않으면 idx = table[idx-1];로 돌려준다.
   3. if(pattern.charAt(i) == pattern.charAt(idx)) 두 위치의 문자가 일치하면  idx값을 올려 table[i]에 저장한다.
2. 최소 광고판 길이 = 광고판 전체 크기(n) - 접미사의 최대 크기(table[n-1])를 출력한다.

 

풀이 코드 

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		String p = br.readLine();
		
		int[] t = makeTable(p);
		System.out.println(n-t[n-1]);
	}
	
	static int[]  makeTable(String pattern) {
		int n = pattern.length();
		int[] table = new int[n];
		int idx=0;
		
		for(int i=1; i<n; i++) {
			while(idx>0 && pattern.charAt(i)!=pattern.charAt(idx)) {
				idx = table[idx-1];
			}
			if(pattern.charAt(i) == pattern.charAt(idx)) {
				table[i] = ++idx;
			}
		}
		return table;
		
	}
}