[Leet Code] 819. Most Common Word(가장 흔한 단어)

 

책에 나온 문제에 추가적인 조건을 더해야 문제를 풀 수 있어요. 

case-insensitive란 대소문자를 구별하지 않는다는 뜻이에요. 그리고 결과는 항상 소문자로 반환해요.

 

📝 풀이

책의 풀이와 달라요. 제가 생각하기에 더 빠른 속도의 알고리즘이에요(O(N^2) -> O(N)).

문제의 조건에 위배되는 입력을 할 경우 무한 루프에 빠질 수 있어요.

문제의 조건에 맞는 입력을 했다는 가정하에 풀이했어요.

def my_solution(paragraph: str, banned: [str]) -> str:
    from collections import Counter
    import re
    banned_dict = dict(Counter(banned))
    paragraph_dict = Counter([word for word in re.sub(r'[^\w]', ' ', paragraph).lower().split()])
    while paragraph_dict:
        if paragraph_dict.most_common(1)[0][0] in banned_dict:
            del paragraph_dict[paragraph_dict.most_common(1)[0][0]]
            continue
        return paragraph_dict.most_common(1)[0][0]

 

 

🧐 고민

1. banned의 처리

banned에 포함되어있는지 여부를 확인하는 방법을 고민했어요. 책에서는 if word not in banned를 하는데, 이렇게 되면 검색마다 O(N)의 로직이 추가가 되는 문제가 생겨요. 그래서 저는 O(1)으로 확인을 하는 방법으로 딕셔너리를 생각했어요.

근거가 필요할 것 같아서 검색을 해봤어요.

파이썬에서 리스트와 딕셔너리 검색 속도 비교를 확인해보면 분명히 딕셔너리와 리스트에서 검색 속도가 차이 나는 것을 확인할 수 있어요. 물론, 이 문제에서는 속도 차이가 크지 않겠지만 알고리즘 풀이의 목적 자체가 조금 더 효율적인 방식을 찾는 것이라 이렇게 작성해봤어요.

 

또한, 딕셔너리를 직접 만들어주는 것이 아니라 내장 함수인 Counter를 통해서 쉽게 구현했어요.

 

2. 전처리 방식

re.sub(r'[^\w]', ' ', paragraph)

위의 코드를 이해하기 위해선 정규표현식에 대한 이해가 필요해요.

 

우선 sub 메서드를 살펴볼게요. python의 정규표현식 모듈 re의 메서드인 sub은 특정 문자열 타입(r'[^\w]')을 두 번째 문자열(' ')로 바꾸는 메서드예요. 물론 세 번째 인자는 검색할 대상 문자열이겠죠. 그래서 위의 식을 다시 해석해보면 아래와 같아요.

 

paragraph라는 문자열에서 r'[^\w]' 타입인 문자열을 찾아 ' '의 공백으로 변경해요.

 

그럼 이제 '^\w'를 볼게요. '^' 표시는 not을 의미하며 '^x'는 문자열 x가 아닌 것을 의미해요. 그럼 '\w'가 아닌 문자열을 의미할텐데, 여기서 w는 word를 의미해요. 즉, 단어가 아닌 문자열을 공백 문자열로 처리해주는 것이므로 쉼표(,), 마침표(.) 등을 공백으로 바꿔줄 거예요.

 

3. most_common

최댓값을 찾는 로직을 고민했어요. 만약에 most_common이 O(N)으로 값을 검색하는 것이면 사실 1번의 고민은 무의미해지거든요. 어차피 반복문 안에 O(N)이니까요. 하지만 Counter의 most_common 메서드는 내부적으로 heap으로 구현되어있어요. 그래서 가장 큰 값을 추출하는데 O(N)이 아니라 O(1)이 되겠죠. 그래서 most_common을 활용했어요.

def most_common(self, n=None):
    '''List the n most common elements and their counts from the most
    common to the least.  If n is None, then list all element counts.

    >>> Counter('abracadabra').most_common(3)
    [('a', 5), ('r', 2), ('b', 2)]

    '''
    if n is None:
        return sorted(self.iteritems(), key=_itemgetter(1), reverse=True)
    return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1))

 

🐾 문제 링크 가기

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