(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 배열을 구하는 함수를 가지고

 

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

 

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

 

 

 

 

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

 

감사합니다!

 

 

소스코드

---