LeetCode [819]: Most Common Word

📌 LeetCode [819]: Most Common Word

🔗 문제 링크

---

문제 설명 📄

주어진 문자열 paragraph에서 가장 많이 등장하는 단어를 반환하세요. 단, banned 리스트에 포함된 단어는 제외해야 합니다.

조건:

• 단어는 알파벳으로만 이루어져 있으며, 대소문자는 구분하지 않습니다.
• paragraph는 문장부호(예: ,, .)를 포함할 수 있으며, 이들을 무시해야 합니다.
• 동일 빈도의 단어가 여러 개 있을 경우, 조건에 따라 가장 앞에 있는 단어를 반환합니다.

---

문제 해결 접근 🧩

1. 데이터 전처리:
   • 문자열 paragraph를 소문자로 변환.
   • 정규식을 이용하여 단어를 추출.
   • Counter를 사용하여 각 단어의 빈도수를 계산.
2. 조건 필터링:
   • banned 리스트에 없는 단어 중 가장 빈도수가 높은 단어를 반환.

---

Solution 💻

import re
from collections import Counter

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        paragraph = re.findall(r'\b[a-z]+\b', paragraph.lower())
        answer = Counter(paragraph)

        for key, _ in sorted(answer.items(), key=lambda x: x[1], reverse=True):
            if key not in banned:
                return key

시간 복잡도 분석 ⏲️

• 정규식으로 단어 추출: (O(n)), 여기서 n은 paragraph의 길이.
• Counter로 빈도수 계산: (O(m)), 여기서 m은 단어의 개수.
• 정렬: (O(m log m)).
• 결과 필터링: (O(m)).
• 최종 시간 복잡도: (O(n + m log m)).

공간 복잡도 분석 🗄️

• 정규식 결과 저장: (O(m)), 단어 리스트 크기.
• Counter 객체: (O(m)), 고유 단어의 개수.
• 총 공간 복잡도: (O(m)).

---

리팩토링 🛠️

개선된 코드

import re
from collections import Counter

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        paragraph = re.findall(r'\b[a-z]+\b', paragraph.lower())
        answer = Counter(paragraph)

        banned_set = set(banned)
        return max((word for word in answer if word not in banned_set), key=lambda x: answer[x])

리팩토링 후 시간 복잡도 ⏲️

• 정규식으로 단어 추출: (O(n)).
• Counter로 빈도수 계산: (O(m)).
• max 필터링 및 탐색: (O(m)).
• 최종 시간 복잡도: (O(n + m)).

리팩토링 후 공간 복잡도 🗄️

• 정규식 결과 저장: (O(m)).
• Counter 객체: (O(m)).
• banned_set: (O(b)), 여기서 b는 banned 리스트의 길이.
• 총 공간 복잡도: (O(m + b)).

---