BOJ 12857 - 홍준이는 문자열을 좋아해

BOJ 12857 - 홍준이는 문자열을 좋아해

어렵게 풀었고 접근법은 비슷했지만 정해는 아니였다.

우선 길이 4 이하의 모든 문자를 해싱해놓으면 $27^4$ 가지의 경우의 수가 나오고 충분히 해싱이 가능하다.

$26^4$로 해서 $ab$의 해시값과 $b$의 해시값이 같아져버리는 실수를 해서 헤맸다.

내가 짠 풀이는 어거지로 최적화를 해서 통과한 것이므로 정해를 보자.

정해는 다음과 같은 나정휘님 슬라이드에서 확인 가능하다.

정해Permalink

$P_a$ 를 $a$ 가 나오는 인덱스들의 정렬된 리스트라고 하자.

문자열 a, b에 대해서 쿼리를 처리할 때 $O(Min(\lvert P_a \rvert, \lvert P_b \rvert)\log {Max(\lvert P_a \rvert, \lvert P_b \rvert)})$ 로 처리를 할 수 있다.

왜냐면 두 개의 문자열 중 더 적게 나오는 것을 쭉 순회하면서 앞 뒤로 붙어있는 나머지 문자열의 위치를 이분탐색으로 구할 수 있기 때문이다.

중복쿼리가 없다고 할 때, $\color{salmon} \displaystyle \sum Min(\lvert P_a \rvert, \lvert P_b \rvert)$ 의 시간복잡도를 생각해보자.

이걸 증명하고 시간복잡도를 이해하는 것이 문제 풀이의 핵심이였다.

일반성을 잃지 않고, $A = \lvert P_a \rvert \le \lvert P_b \rvert = B$ 라고 하자.

$A \le \sqrt{N}$인 경우, 모든 쿼리를 처리하는데 $O(Q \sqrt{N})$ 보다 오래 걸리지 않는다.

$Q=\text{쿼리의 개수}$

$A > \sqrt{N}$ 인 경우, 어떤 문자열들 a가 $S$에서 $\sqrt{N}$ 번 이상 등장한다는 것인데, 이러한 문자열의 개수는 최대 $\sqrt{N}$개 존재한다.

최악의 경우를 상정하고 $(a, b)$ 에 대한 쿼리의 가지수와 시간복잡도를 계산한다.

일단 $b$의 가능한 가지수는 $A \le B$ 이므로 $\sqrt{N}$ 개 이다.

계속 다른 $b$ 가 나오고 $a$ 를 처리해도 $a$ 들의 모든 길이의 합은 $O(N)$ 이므로 $O(N \sqrt{N})$ 으로 시간복잡도가 수렴한다.

여기서 한 가지 더 개선해서 $(a,b)$ 의 가지수는 $O(\sqrt{N} \cdot \sqrt{N})=O(N)$ 에 제한되어 쿼리를 모두 캐시해두면 더 빨라진다.

따라서 이 문제의 전체 시간복잡도는 $O((N + Q)\sqrt{N} \cdot \log N)$ 이 된다.