819. Most Common Word

 String 을 sanitize 하는 부분에서 애를 먹었다. Map traverse 방법은 물론이고 그게 최적인지 잘 모르겠다. 

*Trial and Error

• sanitize 를 하면서 특수문자를 ""로 바꿨더니 "a,b"  가 "ab" 가 되어버렸다.  
• trim 하는것을 까먹어,  "cat" 과 "cat " 이 각각 다른 단어가 되어버렸다.
• "" 가 하나의 단어가 되었다. isEmpty 로 걸렀어야했다.

*Complexity

Paragraph 의 length 를 l 이라고 하고,  banned 의 size 를 s  라고 하면.

• set 에 ban 넣는 O(s)
• 특수문자 sanitize 하는데 O(l)
• split 하는데 O(l)

split  한 단어의 개수를 n 이라 하면,

• HashMap 에 넣으니까, average O(1), worst O(n)
• HashMap traverse 한번 하니까 O(n)

다 더하면

 O(s)+2O(l)+O(1)/O(n)+O(n) 이다.

• average : O(s)+2O(l)+O(1)+O(n) = O(s)+O(l)+O(n)
• worst : O(s)+2O(l)+O(n)+O(n) = O(s)+O(l)+O(n)

결국 O(s+l+n) 의 linear 한 complexity 를 갖는것 같다.

 처음 문제를 보고 접근법을 생각할 때, 이를 Trie 를 통해 접근하면 Paragraph 를 한번만 읽으면 되지 않을까 생각했는데, Trie 구현을 안찾아보고 하기 어려워서 그냥 Map 으로 했다. 가장 성능이 좋은 알고리즘을 보니 역시 Trie 로 접근했다. Trie 를 익숙하게 다룰 줄 알아야겠다.