(JAVA) 백준 1701번 : Cubeditor --- [KMP]

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

1701번: Cubeditor

 

안녕하세요.

 

 

처음에 문자열 탐색 문제라고 생각해서 정석대로 문제를 해결하려 했으나

 

"메모리 초과" ...

 

 

이건 아니다.. 먼가 다른 알고리즘이 있을 것이다 해서 몇 번 서치해봤는데 역시나 존재했다.

 

공부각이다..!

 

찾아보니, 그것은 바로 KMP 알고리즘 이었다.

 

 

간단하게 설명하자면, 그나마 최근에 나온 문자열 탐색 알고리즘 으로,

 

 

  1)  기본적인 문자열 탐색 알고리즘은 O(전체 문자열 길이 * 찾으려는 문자열 길이) 만큼 걸리지만, 이 KMP 알고리즘은 O(전체 문자열 길이 + 찾으려는 문자열 길이) 만 걸리는 효율적인 알고리즘이다.

  2)  이렇게 시간복잡도를 줄일 수 있는 이유는 바로 문자 하나씩 비교하는 것이 아니라 이전에 이미 비교했던 중간 부분을 건너뛰며 비교하기 때문이다.

 

  3)  찾고자 하는 문자열이 왼쪽부터 시작해서 가질 수 있는 모든 문자열들 중,  접두사와 접미사가 같은 문자열의 최대 길이를 구해서 이를 활용하는 알고리즘.

 

 

먼가 말로만 들으면 헷갈린다.

 

3) 의 예시를 들어보겠다.

 

 

ex) tomato 가 있다면

 

접두사 

t

to

tom

toma

tomat

tomato

 

가 되고,

접미사

o

to

ato

mato

omato

tomato

 

가 된다. 여기서, 같은 길이끼리 접두사와 접미사를 비교해보자.

 

t, o -> x

to, to -> o

tom, ato -> x

toma, mato -> x

tomat, omato -> x

tomato, tomato -> 자기자신은 당연히 일치하니까 애초에 비교대상에서 제외됨.

 

그럼, 이 문자열에서 접두사와 접미사가 같은 문자열의 최대 길이는?  ->  2 .

 

 

 

KMP 알고리즘은

 

  1)  "tomato" 에서 왼쪽부터 시작해서 만들 수 있는 문자열(t, to, tom, toma, tomat, tomato) 각각에 대해 위 과정을 수행해서 얻은 값을 배열에 담는다. (보통 pi라고 정한다.)

 

  2)  1)에서 얻은 pi 배열을 가지고 문자열 탐색 중간에 건너뛰기에 활용한다.

 

 

*** 더 자세하게 작성할 수 있지만, 이전에 다른 블로그 포스팅 글이 넘사벽으로 정리되어있어서 링크를 남겨놓겠습니다.

https://bowbowbow.tistory.com/6#comment5168448

KMP : 문자열 검색 알고리즘

 

 

 

그래서 이 문제는 문자열 탐색을 가장한 접두사와 접미사가 같은 문자열의 최대 길이 를 구하는 문제이다.

 

 

즉, 

pi 배열을 구하는 함수를 가지고

 

왼쪽부터 한 글자씩 제거한 문자열을 인자로 넣어 

 

모든 가능한 부분문자열 중에서 접두사와 접미사가 같은 문자열의 최대 길이 를 구하면 된다.

 

 

 

 

그 외 문제 풀이는 하단 소스코드를 참고하시면 됩니다.

 

감사합니다!

 

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	// Cubeditor
	// 문자열 처리 문제
	// KMP 알고리즘
	public class p1701 {
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String str = br.readLine();
	int len = str.length();
	int result = 0;
	// 모든 부분문자열 탐색
	for(int i = 0; i < len; i++) {
	String subStr = str.substring(i, len);
	result = Math.max(result, getMaxBubunLength(subStr));
	}
	System.out.print(result);
	}
	// KMP 알고리즘 사용
	// 해당 문자열 내에 존재하는 부분 문자열 중 접두사와 접미사가 같은 문자열의 최대 길이 구하기.
	// 원래는 pi배열을 리턴하여 문자열 탐색에 KMP 알고리즘으로 사용된다.
	static int getMaxBubunLength(String str) {
	int j = 0; // j : 좌측(접두사) 비교 문자열 인덱스
	int n = str.length(), max = 0;
	int pi[] = new int[n];
	for(int i = 1; i < n; i++) { // i : 우측(접미사) 비교 문자열 인덱스
	while(j > 0 && str.charAt(i) != str.charAt(j)) {
	j = pi[j - 1];
	}
	if(str.charAt(i) == str.charAt(j)) {
	pi[i] = ++j;
	max = Math.max(max, pi[i]);
	}
	}
	return max;
	}
	}

view raw p1701.java hosted with ❤ by GitHub