P14426

[baekjoon-14426] 접두사 찾기

시간 복잡도와 공간 복잡도 사이

이 문제를 단순하게 문자열 배열과 substring 개념을 사용하여 푼다면 간단하여 풀이 속도가 빠르고, 문제에서 주어진 범위가 크지 않기 때문에 무난하게 풀 수 있을 것이다. 하지만 알고리즘은 늘 더 좋은 효율성을 생각해야 하는 문제이기 때문에, 시간 복잡도를 줄일 방법을 생각해봤을 때 Trie를 생각해낼 수 있었다. 특히 접두사를 찾는 문제이기 때문에 아주 적합하다.

두 가지 풀이법을 모두 구현하여 비교해보았다.

• 배열과 startsWith 메서드를 사용한 풀이
• Trie를 사용한 풀이

Trie를 사용했을 때 확실히 시간 복잡도가 줄어들지만, Trie는 공간 복잡도가 크다는 단점이 있다.
두 가지 알고리즘을 모두 알고 상황에 따라 알맞게 적용할 수 있어야 할 것 같다.