[11878] OOP

마지막 수정 시각: 2022-08-14 12:54:17

문제 링크

풀이가 재밌었어서 정리해둔다.

문제 요약

\(N\)개의 단어와 \(Q\)개의 패턴이 주어진다. 각 패턴은 알파벳 소문자와 정확히 한 개의 별표(*)로 구성되어 있고, 별표는 임의의 문자에 대응된다(와일드카드). 각 패턴에 대해 \(N\)개의 문자열 중에 그 패턴과 일치하는 문자열의 개수를 출력하라.

풀이

내가 문제를 풀기 위해 생각한 과정을 순서대로 정리해봤다.

패턴을 *를 기준으로 앞뒤로 나눠보자. 이러면, 각 패턴에 대해 * 앞쪽을 접두사로 가지고 * 뒤쪽을 접미사로 가지는 단어의 개수를 구하는 문제가 된다. 이 때, 접두사와 접미사가 겹치면 안 된다는 점에 주의해야 한다. 즉, ab*ba 같은 패턴이 주어졌을 때 aba 는 이 패턴에 대응되어서는 안 된다(이를 허용하는 경우, 12898번 문제와 동일해진다. 당연히 이 문제를 해결하면 12898번도 해결할 수 있다).

둘을 동시에 해결하기 어려우니 일단 접두사가 같은 것들을 묶는 것부터 시작해보자. 패턴에서 * 앞 부분을 패턴의 접두사라고 하자. 패턴의 접두사 부분만 가지고 트라이(trie)를 구성한다. 이를 패턴 트라이라고 하자. 이제, 이 트라이에 단어 집합도 추가해보자. 패턴 트라이 상에서 각 단어 \(w\)에 대해 \(w\)의 접두사와 가장 길게 일치하는 패턴 접두사에 해당하는 노드에 각 단어를 추가해준다. 이는 각 패턴과 접두사 부분만 일치하는 단어의 집합을 구하는 과정이다.

패턴 트라이를 위와 같은 방식으로 구축하고 나면, 각각의 패턴에 대해 트라이에서 그 패턴에 대응되는 노드의 서브트리에 속하는 단어들을 전부 모은 것이 해당 패턴과 접두사만 일치하는 단어의 집합이 된다.

이제 이 단어의 집합에 대해 접미사가 일치하는 것의 개수를 빠르게 센다면 답을 구할 수 있다. 물론 여기가 제일 어렵다.

접미사 부분도 비슷하게 트라이로 처리한다고 생각해보자. 단어들을 뒤집은 것을 가지고 트라이를 만들면, 그 트라이로부터 패턴의 접미사 길이에 비례하는 시간에 쿼리의 답을 구할 수 있다. 이 트라이를 접미사 트라이라고 하자.

각 노드의 서브트리에서 그 서브트리에 속하는 단어를 전부 모아서 접미사 트라이를 구축하는 과정을 생각해보자. 앞서 말한것처럼 ab*ba 에 aba가 대응되어서는 안되므로, 접미사 트라이에 단어를 추가할 때 현재 노드의 패턴 접두사 뒤쪽에 해당하는 만큼만 접미사 트라이에 추가해줄 것이다.

패턴 트라이의 어떤 노드 \(x\)와 그 노드의 서로 다른 두 자식 \(a\), \(b\)를 생각해보자. \(a\)의 자식에 대해 위 방식대로 답을 구하고, \(b\)의 자식에 대해서도 위 방식대로 답을 구하고 나면, \(a\)에 대응되는 단어와 \(b\)에 대응되는 단어는 모두 \(x\)에도 대응이 된다. 한 번 접미사 트라이를 계산한 걸 활용해서 이를 빠르게 계산할 수 없을까?

일단, \(a\)의 접미사 트라이와 \(b\)의 접미사 트라이중 크기가 더 큰 것을 고르자. 이 접미사 트라이를 그대로 \(x\)의 트라이라고 하고, 여기에 \(a\)의 접미사 트라이에 대응되는 단어들을 추가해준다. 이런 식으로 추가할 경우, small to large 테크닉과 동일한 원리에 의해 전체 단어의 길이 합을 \(L\)이라고 했을 때 \(O(LlogL)\) 시간에 재구축이 가능해진다. 여기에 추가적으로, \(x\)의 패턴 접두사 길이는 항상 \(a,b\)의 패턴 접두사 길이보다 짧으므로, 기존에 접미사 트라이에 추가되어 있던 단어에 대해 트라이에 반영해야하는 만큼 더 반영해주는 작업도 필요하다. 이 과정은 기존에 접미사 트라이에 추가되어있던 단어들에 대해 그 단어들의 몇번째 위치까지 추가됐는지, 그리고 그 시점에 노드는 무엇이었는지 정보를 같이 저장해주면 \(O(L)\) 만큼만 작업이 필요하므로 충분히 빠르다.

이 논리대로 구현해보면, 시간복잡도 상으로 \(O(LogL + NlogN + Q)\) 가 되지만, 트라이가 상수가 꽤 커서 통과되지 않는다(시간, 공간 모두).

여기서 추가적인 최적화를 고민해보자. 접미사 트라이를 다 따로따로 만들고 합치는 부분이 가장 느린데, 이걸 따로따로 만들지 않고 전체에 대해 단일 접미사 트라이만 관리할 수는 없을까? 결국 패턴 트라이의 어떤 서브트리에 대응되는 단어들에 대해서만 쿼리한 결과를 얻고 싶은 건데, 이 부분에 집중해보자. 단일 접미사 트라이를 관리하고, 이 접미사 트라이에 각 패턴 노드를 방문할 때마다 그 패턴 노드에 붙어있는 단어 집합을 접미사 트라이에 추가해준다.

이제 여기서 그냥 쿼리하면, 내 서브트리에 대응되는 답 뿐만 아니라 내 서브트리보다 이전에 방문한 노드의 답들도 전부 계산이 되는 부분이 문제가 된다. 이 부분에서, euler tour trick의 논리를 적용한다. 각 노드를 방문한 순서대로 배열에 기록하면, 각 서브트리는 배열상의 한 구간에 대응된다. 현재 서브트리에 대응되는 배열 상의 구간을 \(L\)에서 \(R\)이라고 하자. 아래의 과정을 거치면 하나의 접미사 트라이만 관리해도 답을 구할 수 있음을 알 수 있다.

1. 현재 노드에 처음 방문하는 시점에서, 접미사 트라이에 내 노드에 대응되는 쿼리의 답을 구한다. 이 답은 \(0 \dots L-1\)번째 노드에 대응되는 단어들만 이용했을 때 쿼리에 대한 답과 같다.

2. 현재 노드에 대응되는 단어들을 접미사 트라이에 추가하고, 내 노드의 하위 노드들에 대해 동일한 과정을 반복한다.

3. 반복이 끝나고 나면, 다시 접미사 트라이에 내 노드에 대응되는 쿼리의 답을 구한다. 이 답은 \(0 \dots R\)번째 노드에 대응되는 단어들만 이용했을 때 쿼리에 대한 답과 같다.

4. 3에서 구한 값에 1에서 구한 값을 빼면 원하는 \(L\)부터 \(R\)까지 구간의 단어들만 이용한 답이 된다(부분합의 논리).

따라서, 위 과정을 통해 단순한 dfs로 하나의 접미사 트라이만 관리하면서 원하는 답을 모두 구할 수 있다. 이 때 기존에 추가된 단어들에 대해 패턴 접두사 길이가 더 짧아지면 짧아지는만큼 당겨주는 로직이 필요한데 이는 set 등의 자료구조를 이용해서 각 단어가 어느 길이까지 추가된 상태인지를 관리하면 어렵지 않게 구현할 수 있다. 전체 시간복잡도는 \(O(L + (N+Q)logN)\) 정도가 되는 것 같다. 하나의 접미사 트라이만 쓰는 최적화를 하는 단계의 발상이 재밌었기 때문에 정리해보았다.