[LeetCode] 819. Most Common Word (JS)

https://leetcode.com/problems/most-common-word/

Most Common Word - LeetCode

핵심 아이디어

• split() 에 정규표현식 /W+/ (not word, 1 or more) 를 사용하여 알파벳만 배열 나눌 수 있다
• O(N)인 Array.includes() 보다는 O(1)인 Map.has()가 시간이 적게 걸린다

 

복잡도

N = 단어의 개수라면,

• 시간 복잡도: O(N)
  
  • filter O(N) * Map.has O(1)
  • reduce O(N) * (Map.has O(1), Map.set O(1) )
• 공간 복잡도: O(N)
  
  • words, counter

 

설명

"금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표 쉼표 등) 또한 무시한다"

주어진 문자열의 전처리가 중요한 문제이다. 대소문자 구분을 하지 않으니 toLowerCase()로 소문자로 바꿔 주고, 띄어쓰기로 구분된 단어이면서 구두점도 포함하지 않으니 split(/W+/)로 알파벳이 아닌 문자를 기준으로 단어를 나눈다.

banned가 배열로 주어지는데, 반복문 한 번 돌 때마다 단어가 banned에 포함되는지 검사해야 하니 banned를 hashMap으로 바꿔놓으면 최적화할 수 있다. O(N)인 Array.includes() 보다 O(1)인 Map.has() 가 시간상 유리하기 때문이다.

단어가 나온 횟수도 Map()에 저장하였다. hashMap.get(word)로 이전까지 세었던 단어의 개수를 O(1)시간에 불러올 수 있기 때문이다. 단어의 횟수를 저장한 뒤에는 .entries()로 배열로 변환한 뒤 .reduce( (prev, cur) => prev > cur ? prev : cur ) 의 형태로 value가 max인 key를 구하였다.

 

코드 (Javascript)

/**
 * @param {string} paragraph
 * @param {string[]} banned
 * @return {string}
 */
var mostCommonWord = function(paragraph, banned) {
    const bannedSet = new Set(banned);
    
    const words = paragraph.toLowerCase().split(/\W+/).filter(word => !bannedSet.has(word) && word !== "");
    const counter = words.reduce((hashMap, word) => {
        if(!hashMap.has(word)) {
            hashMap.set(word, 1);
            return hashMap;
        }
        
        hashMap.set(word, hashMap.get(word) + 1);
        return hashMap;
    }, new Map());
    
    const commonWord = [...counter.entries()].reduce( (curCommonPair, pair) => curCommonPair[1] < pair[1] ? pair : curCommonPair )[0];
    
    return commonWord;
    
};