cyhh333   2년 전

KMP로 코드 구현하였는데, 

아무리 노력해도 시간초과때문에 13%를 넘어갈 수가 없었습니다..


어떻게 구현해야할지 막막해서 다른 분들 어떻게 푸셨나 탐색을 해보다가

스택으로 푼 코드를 발견하였습니다. 

해당 코드를 보고는.. 현타가 조금 오더군요 ..ㅎㅎㅎ



스택으로 푼 코드가 제 KMP 코드보다 시간복잡도가 작은 이유는,

제 KMP 코드의 del 연산이 시간을 많이 잡아먹기 때문일까요?

f52985   2년 전

맞습니다. 길이 N짜리 list에 대한 del 연산의 경우는, 시간복잡도가 O(N)입니다. (https://wiki.python.org/moin/T...)

따라서 O(N)짜리 del 연산이 최대 O(N)번 일어날 수 있으므로 (입력이 aaaaaa.....a 와 a 인 경우), kmp를 이용한 알고리즘의 시간복잡도는 O(N^2)이 되겠네요.

반면 스택을 이용한 풀이의 경우는 pop 연산과 push 연산만 각각 최대 N번씩 일어나므로 시간복잡도는 O(N)이 됩니다.

댓글을 작성하려면 로그인해야 합니다.