04. Most Common Word

🎯 leetcode - 819. Most Common Word

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 4번 문제

📌 날짜

2020.01.15

📌 시도 횟수

6 try

💡 Code

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        paragraph = re.sub("[,.?!';@#$%^&*()]", " ", paragraph)
        arr = {}
        max = 0
        max_str = ""
        for x in paragraph.split():
            if x.lower() in banned:
                arr[x.lower()] = 0
            else:
                if x.lower() in arr:
                    arr[x.lower()] += 1
                else:
                    arr[x.lower()] = 1
        for x in paragraph.split():
            if max < arr[x.lower()]:
                max = arr[x.lower()]
                max_str = x.lower()
        return max_str

💡 문제 해결 방법

1. paragraph를 정규 표현식으로 특수 문자를 " "으로 치환하여 바꾼다.
2. 각각의 단어와 빈도가 key, value로 사용되는 arr(dict)를 선언한다.
3. paragraph를 split()으로 각각의 단어로 분리한다.
4. 만약 단어가 banned에 포함돼있을 경우 arr[단어] = 0 이다. (빈도가 0)
5. 아니라면, 새로운 단어일 경우에는 1을 할당, 이미 있는 단어일 경우에는 1 추가해준다.
6. 다시 paragraph의 각 단어를 split()으로 분리한 후,
value가 max인 단어의 key를 return 한다.

💡 새롭게 알게 된 점

- re.sub('패턴', '바꿀문자열', '문자열', 바꿀횟수)

❌ (한번에 맞추지 못한 경우) 오답의 원인

✔ 오류 원인 1 : banned가 빈 리스트[]일 경우에 max를 구할 수 없었음
→ 모든 케이스를 충분히 고려하지 않음

✔ 오류 원인 2 : 처음에 특수 문자를 ""으로 치환했더니 오류가 발생함
⊙ 예시) 입력이 "a,b,c,d,e"인 애들이 "abcde"로 되어 하나의 문자열로 처리됨
→ 모든 케이스를 충분히 고려하지 않음 (""가 아닌 " "으로 치환해야 오류가 발생하지 않음) 

✔ 오류 원인 3 : dict로 처리할 때 banned의 key를 아예 제거해버렸더니
나중에 계산할 때 x가 banned일 경우 arr[x.lower()]의 연산이 불가능해짐
→ 애초에 x를 입력값에 대하여 banned를 제외한 리스트가 되도록 처리했다면...

✔ 오류 원인 4 : sub할 특수문자의 종류가 모두 제공되지 않음
→ 조건 중 "단어를 출력한다"를 [문자열에서 모든 특수문자를 제거한다]가 아닌,
[문자열에서 "단어 문자를 제외한 문자를 제거한다"]로 처리해서 풀 수는 없을까?

---

😉 다른 풀이

📌 하나. 리스트 컴프리헨션 + defaultdict(int) 사용

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        words = [
            word  # 아래 조건들을 만족하는 word의 list
            for word in re.sub(r"[^\w]", " ", paragraph) # 단어 문자들에 대하여
            .lower().split()  #소문자로 바꾼 것의 공백 기준 split()
            if word not in banned  # 단 금지된 단어는 제외함
        ]
        counts = collections.defaultdict(int)
        for word in words:
            counts[word] += 1
        return max(counts, key=counts.get)

💡 새롭게 알게 된 점

✔ collections.defaultdict(int)
  - defaultdict를 활용해 다음과 같이 기본값을 ‘int’ 로 선언해주고,
  기존에 없던 key를 호출하면 해당 key가 0으로 자동 초기화된다.
  - 즉, 이 방법을 이용하면 위의 사전의 기본값 처리 코드를 완전히 제거할 수가 있다.
  - 또한, lambda 식을 사용해 원하는 초기값을 지정할수도 있다.
      >>> d_dict = defaultdict(lambda: 'default value')
      >>> d_dict["a"]
      'default value'
      
✔ return max(counts, key = counts.get)
  - max에 key 값을 설정할 수 있음을 알았다.
  - defaultdict.get : Return the value for key if key is in the dictionary, else default.
  - defaultdict.get이라는 함수가 해당 dict의 value를 반환하는 함수임을 알게 되었다.
      
✔ 정규식(re)과 re.sub(r'[^\w]', ' ', 문자열)
  - ^는 not을 의미한다.
  - \w는 모든 단어 문자를 의미한다.
  - 따라서 [단어 문자가 아닌 모든 문자를 공백으로 치환]하는 코드이다.

정규 표현식 r(Raw String)

• re.sub(r'[^\w]', ' ', 문자열)
• 컴파일 해야하는 정규식이 Raw String(순수한 문자)임을 알려줄 수 있도록 한다.
• 만약 re.colmile('\section')의 경우 \s는 원래 공백 문자를 의미하는 문자로 인식되어 제대로 된 결과를 찾지 못한다. 따라서 이런 경우에는 \\section이라고 작성해야 한다.
• 근데 헷갈리잖아!! 그래서 파이썬에서는 특수하게 r을 사용하면 \section처럼 \(백슬래쉬) 한 개만 사용해도 자동으로 \\section을 쓴 것과 같은 효과를 얻을 수 있다.
• 즉, 정규 표현식에 [\t, \n, \r, \s] 등의 문자가 있어도 이를 순수한 문자(Raw String)처럼 처리하도록 돕는 것이 바로 r이다.

---

📌 둘. Counter 객체

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

💡 새롭게 알게 된 점

✔ collections.Counter() : 컨테이너에 동일한 값의 자료가 몇개인지를 파악하는데 사용하는 객체
- collections.Counter()의 결과값(return)은 딕셔너리 형태로 출력된다.
▷ 예시) 
→ >>> Counter('hello world') 
→ Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'W': 1, 'r': 1, 'd': 1}) 반환

✔ collections.Counter()의 most_common() 메소드
- 데이터의 개수가 많은 순으로 정렬된 배열을 리턴한다.
▷ 예시)
→ >>> Counter('hello world').most_common()
→ [('l', 3), ('o', 2), ('h', 1), ('e', 1), (' ', 1), ('w', 1), ('r', 1), ('d', 1)] 반환

collections.Counter() & most_common(n)

• Counter()
  A Counter is a dict subclass for counting hashable objects. It is a collection where elements are stored as dictionary keys and their counts are stored as dictionary values.

from collections import Counter
>> c = Counter()  # a new, empty counter
>> c = Counter("gallahad")  # a new counter from an iterable
>> c = Counter({"red": 4, "blue": 2})  # a new counter from a mapping
>> c = Counter(cats=4, dogs=8)

Counter()
Counter({'a': 3, 'l': 2, 'g': 1, 'h': 1, 'd': 1})
Counter({'red': 4, 'blue': 2}) 
Counter({'dogs': 8, 'cats': 4})

• most_common([n])
  Return a list of the n most common elements and their counts from the most common to the least. If n is omitted or None, most_common() returns all elements in the counter. Elements with equal counts are ordered in the order first encountered:

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

✔ 추가적인 설명은 여기에서😊