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

yunan·2021년 1월 14일

leetcode 파이썬알고리즘인터뷰

🐬 알고리즘 풀이 🐬

목록 보기

38/74

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

문제

return the most frequent word that is not in the list of banned words.

금지된 단어를 제외한 가장 빈번한 단어를 반환하세요.

Input: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"

입출력

Input : logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

✍️ 풀이

words의 불필요한 문자들을 re.sub로 빼준다. 남은 문자열의 소문자로 변환 후 단어 별로 나누게 된다.
이 후 words리스트를 word 단위로 반복해 가장 많이 나온 수를 딕셔너리를 통해 구한다.
딕셔너리를 딕셔너리의 값의 순서로 정렬하면 딕셔너리의 첫번째 인덱스 값이 가장 많이 나온 단어이다.

🛠 코드

리스트를 원소를 앞-뒤로 검사하는 가장 기본적인 풀이방법이다.

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        dic = dict()
        # 문장에서 !?,'.; 를 빼고 ' '(space)로 치환한다. 그 후 split()을 한 단어 리스트에서 단어가 banned가 아닌것만으로 리스트를 만든다.
        words = [word for word in re.sub(r'[!?,\'.;]', ' ', paragraph).lower().split() if word not in banned]
        for word in words:
            if not dic.get(word):
                dic[word] = 1
            else:
                dic[word] += 1
        # value로 딕셔너리 소팅하기!! => 일단 소팅할 인자값으로는 dic.items()를 넣어주고 key값으론 value를 넣어준다( lambda x : x[1] )
        # 오름차순 정렬을 위해 reverse=True 추가
        dic = sorted(dic.items(), key=lambda x: x[1], reverse=True)
        return dic[0][0]

✍️ 다른 풀이

re.findall을 통해 re.sub와는 반대로 단어만을 찾아서 사용할 수 있다.
Counter객체에 리스트를 넣으면 해당 리스트의 값의 갯수를 비교해 딕셔너리를 가진 리스트를 반환한다.

🛠 다른 코드

리스트를 원소를 앞-뒤로 검사하는 가장 기본적인 풀이방법이다.

def mostCommonWord(self, p, banned):
        ban = set(banned)
        words = re.findall(r'\w+', p.lower())
        return collections.Counter(w for w in words if w not in ban).most_common(1)[0][0]