[BOJ 5052]

문제 바로가기 : https://www.acmicpc.net/problem/5052
문제 설명은 위 링크에서 확인해주시길 바랍니다.

트라이 알고리즘 설명은 여기에서 참고했습니다. 감사합니다.

Solution

Trie algorithm

앞서 언급했지만 저는 여기에서 참고했습니다.
잘 정리돼있어서 트라이 알고리즘에 대해 처음 접하는 분들이라면 많은 도움이 될거라고 생각합니다.

문자열을 빠르게 탐색한다는 장점이 있으나 공간복잡도가 문자열 길이에 따라 크게 커질 수 있습니다.

review

번호의 길이는 각각 다를 수 있으며 모든 번호가 어디에 포함되지 않도록 모두 독립적이어야 한다.
문제에서는 일관성이 있다고 표현하고 있다. 답은 일관성 여부를 나타내면 된다.
문자열의 마지막은 finish가 true여야 하는데, 인자를 string으로 고치다보니 소스를 조금 수정했다.
새롭게 입력하는 경우는 문제가 없지만 겹치는 경우 next[]가 NULL이 아니다! 이 때는 true를 갱신하지 못하게 했다.