devbelly

문제 https://www.acmicpc.net/problem/3080 알고리즘 Trie 풀이 관찰이 필요한 문제입니다. 예제들을 그림으로 그려 예제 입출력을 이해하도록 합시다. 이를 통해 문제의 답은 (트라이의 자식 수 + 해당 트라이에서 끝나는 단어)의 팩토리얼들의 곱이라는 점을 알아낼 수 있습니다. 이렇게 문제를 풀게 되면 메모리 초과가 발생하게 됩니다. Trie? 선형시간에 원하는 문자열을 찾아낼 수 있는 자료구조입니다. 이를 가능케 하는 것은 각각의 트라이마다 모든 문자들을 가리키는 포인터를 저장하고 있기 때문입니다. 이 때문에 많은 메모리를 사용한다는 단점이 있는 자료구조입니다. 따라서, 필요하지 않은 문자열을 제거해야합니다. Suffix Array & LCP에서 봤듯이, 주어진 문자열을 정렬..