Most Common Word

LeetCode의 Most Common Word 문제다.

Most Common Word - LeetCode

이전 포스트에 이어 문자열 처리에 관련된 문제인데 문장을 단어 단위로 구분해야 하기 때문에 여간 까다로운 문제가 아니었다. 그래서인지 Easy 난이도임에도 불구하고 비추가 더 많은 것 같은데... 일단 결과적으로는 풀이를 참고했기 때문에 완전히 스스로의 힘으로 푼 건 아니지만 생각을 조금 전환할 수 있는 계기가 됐다.

 

문제는 단순히 문장(paragraph)과 금지된 단어의 리스트가 주어진다. 그리고 문장의 단어들 중에서 금지된 단어가 아닌 단어 중 가장 많은 빈도를 가지는 단어를 반환하는 문제인데 단순히 공백으로 분리해서 빈도수를 체크하면 되는 게 아닌가 싶지만 문장에는 '!'나 '.', ',' 같은 특수문자들도 포함되어 있기 때문에 이를 제거해야 한다.

 

그러나 모든 경우의 수를 따져서 제거하는 것은 현실적으로 어렵기 때문에 시도할 수 있는 하나의 방법은 주어진 문자열을 하나하나 확인해서 공백 문자거나 알파벳 문자인 경우에는 그대로 리스트에 삽입하고 그렇지 않은 경우, 예를 들어 ','나 '?' 같은 특수문자의 경우 공백 문자로 삽입한 다음 join 하는 것이다. 예를 들어 "a, b, c, d" 같은 문자열이 주어진다면 ','가 공백 문자로 치환되어 "a", " ", " ", "b", " ", " ", "c", " ", " ", "d"를 리스트에 삽입하는 것이다. 이를 join 하여 하나의 문자열로 합한 다음 다시 공백 문자로 분리(split)하여 적절한 단어(빈 문자열이 아닌 것)만 따로 리스트에 저장하면 특수문자를 지울 수 있을 것이다.

 

아니면 정규표현식을 이용하여 알파벳이 아닌 문자들을 전부 제거하는 방법도 있는데 정규표현식은 바로 떠올리기도 힘들기 때문에 이걸 코딩 테스트에서 써먹을 수 있을까? 하는 의문이 들어서 일단 보긴 하지만 외우진 않으려고 한다.

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        word_count = dict()
        
        # 알파벳 문자(isalpha)거나 공백 문자(isspace)인 경우 소문자로 치환(lower)해서 리스트에 삽입.
        # 이후 join 메서드를 이용해 리스트에 담긴 단어들을 문자열로 변환.
        clear_paragraph = "".join([char.lower() if char.isalpha() or char.isspace() else " " for char in paragraph])
        # 문자열을 공백을 기준으로 분리하여 단어로 만든 후 빈 단어는 제외하고 다시 리스트에 삽입.
        word_list = [word.lower() for word in clear_paragraph.split(" ") if len(word) > 0]
        
        # 단어 리스트의 각 단어들마다 개수를 세서 저장.
        for word in word_list:
            if word in word_count:
                count = word_count.get(word)
                word_count.update({word:count+1})
            else:
                word_count.update({word:1})
        
        # 사전의 키-값 중 값을 기준으로 정렬, 금지단어가 아닌 가장 높은 빈도의 단어를 반환.
        sorted_word = sorted(word_count, key=lambda word: word_count[word], reverse=True)
        for word in sorted_word:
            if word not in banned:
                return word

실행 결과는 하위 35% 정도의 속도(40ms)로 썩 만족스럽진 않았는데 상위권은 정규표현식 풀이가 많은 것으로 보아 시간 복잡도로 따진다면 정규표현식이 더 효율적인 것 같다. 하지만 그 포맷을 기억하기도 어렵고 하니...

 

책에서 읽은 팁인데 이렇게 개수를 세기 위한 사전 자료형을 사용할 때는 defaultdict()를 사용해서 기본값을 가진 사전 자료형을 사용할 수 있다고 한다. 위처럼 사전 자료형에 키가 있는지 확인하는 과정이 필요 없기 때문에 더 편한 것 같다. 그리고 괄호([])를 사용한 인덱싱과 '+=' 같은 병합 연산자를 사용하면 더 짧게 코드를 작성할 수 있다.

...
        word_count = defaultdict(int)
...
        for word in word_list:
            word_count[word] += 1
...

 

익숙하진 않지만 collections 모듈의 Counter 클래스를 활용하면 좀 더 간단하게 작성할 수 있다. 이 클래스는 딱 이렇게 갯수를 세는 용도에 적절한 클래스로 사용 예시를 보이면 다음과 같다.

>>> words = ['a', 'b', 'c', 'd', 'd', 'a', 'b', 'b', 'b', 'e']
>>> counts = collections.Counter(words)
>>> counts
Counter({'b': 4, 'a': 2, 'd': 2, 'c': 1, 'e': 1})

Counter 클래스를 사용하면 위처럼 객체와 그의 빈도수가 저장된 사전을 반환하는데 여기서 most_common이라는 메서드를 활용할 수 있다. 이 메서드는 말 그대로 가장 빈도가 높은 객체를 매개변수로 전달된 개수만큼 출력해주는 메서드다.

>>> counts.most_common(1)
[('b', 4)]
>>> counts.most_common(2)
[('b', 4), ('a', 2)]
>>> counts.most_common(3)
[('b', 4), ('a', 2), ('d', 2)]

물론 이 경우 금지된 단어를 미리 리스트에서 제거해야 할 것이다. 그 후 most_common(1)처럼 메서드를 호출하여 가장 빈도가 높은 객체(여기서는 단어)를 추출, 튜플에서 첫 번째 원소인 단어를 반환하면 되는 것이다. 이 경우 소스 코드는 다음과 같다.

import collections

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        clear_paragraph = "".join([char.lower() if char.isalpha() or char.isspace() else " " for char in paragraph])
        word_list = [word.lower() for word in clear_paragraph.split(" ") if len(word) > 0 and word not in banned]
        
        word_count = collections.Counter(word_list)
        return word_count.most_common(1)[0][0]

하지만 실행시간이나 메모리 사용량에는 별 차이가 없으니 외우기 쉬운 것을 사용하면 될 것이다.