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 를 익숙하게 다룰 줄 알아야겠다.
Comments
Post a Comment