leetcode 819. Most Common Word 리트코드 819. 가장 흔한 단어 문제 풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

문제 

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

 

입력 : string data type인 paragraph , list data type인 banned

출력: string data type

 

문제 요약: 가장 자주 등장하는 단어를 고른다. 단, 따로 뽑아 놓은 banned 리스트에 있는 단어는 제외하고.

생각 과정

1. 하나의 문장을 단어 단위로 쪼개고, (.split())

2. banned 리스트에 포함된 단어들은 빼고, (if x not in banned)

3. 단어가 등장할 때마다 count를 올려서 단어 - key 등장 횟수 - value 쌍의 dictionary를 만들어,

4. value 수가 가장 큰 key를 뽑아내기

 

여기서 3번 과정은 지난 번에 풀었던 <완주하지 못한 선수> 문제를 풀 때 익혔던 .get을 활용해서 해결했고,

4번이 까다로웠다. 딕셔너리의 경우 key를 가지고 색인하기는 쉽지만 value를 가지고 색인하기는 어렵고, 또 정렬해서 가장 큰 값도 뽑아야 하기 때문.

구글 검색해서 한 블로그를 참고했다. sorted() 함수를 쓰는데 key = lambda 함수 를 활용한다.

 

풀이

먼제 내가 제출한 코드는 다음과 같다.

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        words = [word for word in re.sub('[^\w]',' ',paragraph).lower().split( ) if word not in banned]
        word_dict = {}
        for word in words:
            word_dict[word] = word_dict.get(word,0) + 1
        frequent = sorted(word_dict.items(), key=lambda x: x[1], reverse=True)
        return frequent[0][0]

결과는 통과. runtime은 36 ms.

 

그런데 책의 풀이를 확인해보니 for 문이나 sorted를 활용하지 않는 훨씬 간편한 방법이 있었다.

바로 파이썬 라이브러리 collections 를 활용하는 것.

collections.Counter()는 내가 for문으로 만든 딕셔너리와 완전히 같은 결과를 출력한다.

즉, 동일한 값의 자료가 몇 개인지 파악해서 key - value 형태로 출력한다.

그리고 collections.Counter()의 내장함수 most_common() 은 내가 만든 sorted 문과 완전히 같은 결과를 출력한다.

즉 가장 빈도수가 높은 순으로 key-value tuple을 반환한다.

 

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

이렇게 할 경우 runtime은 32 ms.

 

아주 큰 차이가 난 것은 아니었지만, 평소에 잘 사용하지 않던 collections 라이브러리를 접해볼 수 있었다.