[String Manipulation] Most Common Word

박상길님의 <파이썬 알고리즘 인터뷰>를 보며 문제를 풀고 정리한 것입니다.

가장 흔한 단어 (Most Common Word)

문제 출처: https://leetcode.com/problems/most-common-word/

 

문제

Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique.
The words in paragraph are case-insensitive and the answer should be returned in lowercase.
 
Example 1:
Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"

Constraints:
1 <= paragraph.length <= 1000
paragraph consists of English letters, space ' ', or one of the symbols: "!?',;.".
0 <= banned.length <= 100
1 <= banned[i].length <= 10
banned[i] consists of only lowercase English letters.

문제 이해 (사고의 흐름)

1. 이 문제에는 자잘한 조건들이 많으니까 잘 체크해야겠다.

2. paragraph를 소문자로 바꾼다.

3. split한다. 뭘 기준으로? 빈칸과  "!?',;.".  이것들로. 

4. for loop을 돌면서 banned에 포함되지 않은 것을 cnt dictionary에 나온 횟수를 넣어준다. 

5. cnt dictionary에서 value가 가장 큰 것 하나를 return 한다. 

 

첫 번째 풀이

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        words = re.split(r'[^\w]', paragraph.lower())
        banned_word = [word for word in words if word not in banned]

        cnt = {}
        for word in banned_word:
            if word == '':
                continue
            if word in cnt:
                cnt[word] += 1
            else:
                cnt[word] = 1

        return sorted(cnt.items(), key=(lambda x: x[1]))[-1][0]

 

그런데 for loop돌고 그 결과에서 최대 횟수를 가진 단어를 return하는 부분이 굉장히 python 스럽지 않고 지저분 한 것 같다. 

더 python 스럽게 짤 순 없을까??

 

collections 모듈

횟수를 counting하는 것은 collections모듈의 defaultdict를 사용할 수 있다. 

공식문서에 나와있는 defaultdict 설명을 보면 defaultdict에 int 기본값이 자동으로 부여되게 하면 기본적으로 0부터 시작되도록 하기 때문에 counting에 매우 유용하다고 나와있다. 

Setting the default_factory to int makes the defaultdict useful for counting (like a bag or multiset in other languages):

>>> s = 'mississippi'
>>> d = defaultdict(int)
>>> for k in s:
...     d[k] += 1
...
>>> list(d.items())
[('i', 4), ('p', 2), ('s', 4), ('m', 1)]

When a letter is first encountered, it is missing from the mapping, so the default_factory function calls int() to supply a default count of zero. The increment operation then builds up the count for each letter.
The function int() which always returns zero is just a special case of constant functions.

 

그리고 dictionary 변수인 cnt에서 값이 가장 큰 키를 가져오려면 max()함수에 key를 지정해 argmax를 간접적으로 추출할 수 있다. 

max(cnt, key = cnt.get)

 

collections.defaultdict(int)와 max함수를 사용

import re
import collections

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        banned_word = [word for word in re.sub(r'[^\w]', ' ', paragraph)
                                            .lower().split() 
                                                if word not in banned]
        
        cnt = collections.defaultdict(int)
        for word in banned_word:
            cnt[word] += 1

        return max(cnt, key=cnt.get)

 

collections.Counter 사용

개수를 처리하는 부분은 Counter를 사용하면 좀 더 깔끔하게 처리할 수 있다.

banned_word = [word for word in re.sub(r'[^\w]', ' ', paragraph)
               .lower().split()
               if word not in banned]

cnt = collections.Counter(banned_word)
print(cnt)

이렇게 하면 결과는
Counter({'ball': 2, 'bob': 1, 'a': 1, 'the': 1, 'flew': 1, 'far': 1, 'after': 1, 'it': 1, 'was': 1})

이렇게 나온다 . 그 후

 

word에서 가장 흔하게 등장하는 단어의 첫 번째 값을 most_common(1)로 출출하면 [(key, value)] 의 형식이 되고, 이 중 key값을 리턴하기 위해선 [0][0]에 접근하면 된다. 

import re
import collections

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        banned_word = [word for word in re.sub(r'[^\w]', ' ', paragraph)
                                            .lower().split() 
                                                if word not in banned]
        
        cnt = collections.Counter(banned_word)
        return cnt.most_common(1)[0][0]

 

정리

• 데이터의 개수를 셀 때 collections모듈의 counter 클래스가 유용하다. 

 

Reference

https://docs.python.org/3.3/library/collections.html#defaultdict-objects

[Python]알고리즘 문제풀이6(collections 모듈)