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

Popular posts from this blog

삼성전자 무선사업부 퇴사 후기

개발자 커리어로 해외 취업, 독일 이직 프로세스

코드리뷰에 대하여