819. Most Common Word

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

Most Common Word - LeetCode

난이도 : easy

문제

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

1. 입력으도 들어오는 문자열을 소문자로 치환한다.

2. stringstream 을 활용하여 paragraph 문자열을 ' ' 단위로 분리하며 map 삽입하고 value 를 증가한다.

3. 문자열의 끝까지 반복하며 value 의 값이 가장 큰것이 정답이 된다. 만약 banned 에 속한 문자이면 map 에 삽입하면 안된다.

 

map 자료형을 사용하였음으로 시간 복잡도는 n * log2(n) 문자열의 총길이 1000을 넘지 않으니 공간복잡도 또한 최대 O(N) 이다.

 

코드

class Solution {
public:
    string mostCommonWord(string paragraph, vector<string>& banned) {
        
        // 주어진 pragrpaph 에서 공백이 아니고 알파벳이면 소문자로 치환
        for(auto&c : paragraph)
		    c = isalpha(c) ? tolower(c) : ' ';

        string str, res;
        unordered_map<string, int> freq;
        unordered_set<string> b(banned.begin(), banned.end());
        
        
        stringstream ss(paragraph);

        // stringstream 으로 문자열을 분리하면서 unorded_map 키와 벨류를 추가
        // value 값이 크다면 가장 빈도가 높은 문자로 판단.
        while(ss>>str)
            if(b.count(str)==0 && freq[res]<++freq[str]) 
                res = str;

        return res;
    }
};