[BOJ]4358번: 생태학

문제: https://www.acmicpc.net/problem/4358 

---

map이나 트라이 알고리즘으로 해결할 수 있는 문제입니다.

 

정해는 트라이입니다.

위 코드가 트라이로 해결한 방법이고, 아래 코드가 map으로 해결한 방법입니다.

 

 

둘 사이에 왜 이런 시간 차이가 생기냐면,

 

나무 이름: T (30)

나무의 종류 갯수: N (10,000)

주어지는 나무의 그루 수: M (1,000,000)

 

트라이를 사용 경우:

하나의 나무를 트라이에 넣을 때 O(T) 만큼의 시간이 걸립니다.

 

map을 사용하는 경우:

하나의 나무를 map에 넣을 때 O(logN * logN)의 시간이 걸립니다.

(나무가 map에 있는지 체크하는데 logN, 그리고 map에 나무를 넣는데 logN)

 

그러므로 트라이 알고리즘의 시간복잡도는 O(M * T)

맵을 사용한 알고리즘의 시간복잡도는 O (M * (logN * log N)) 입니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ4358.cc