본문 바로가기
Programming/알고리즘 파이썬 문제풀이

[Python/LeetCode] 819. Most Common Word

cuffyluv 2025. 1. 21. 17:48

https://leetcode.com/problems/most-common-word/description/

가장 흔한 단어.

금지된 단어를 제외하고, 가장 흔하게 등장하는 단어를 출력해라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표 등) 또한 무시한다.

정답은 소문자 형태로 출력되어야 한다.

 

입력 : 원본 문자열 str, 금지된 단어 리스트 banned

출력 : 가장 흔하게 등장하는 단어 하나로 이루어진 문자열

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

 

 

직관 및 접근

잠깐!!

해당 글에 사용된 세 함수 및 메서드에 대해, 본 블로그에 따로 글로 정리했으니

아래 글들을 읽으면서, 이해가 잘 안되는 부분이 있다면 아래 링크 글을 읽어보자!!

https://cuffyluv.tistory.com/121

 

[Python] 문자열 치환 메서드 성능 비교 - str.replace(), re.sub(), str.translate()

https://cuffyluv.tistory.com/120 [Python/leetcode] 819. Most Common Wordhttps://leetcode.com/problems/most-common-word/description/가장 흔한 단어.금지된 단어를 제외하고, 가장 흔하게 등장하는 단어를 출력해라. 대소문자

cuffyluv.tistory.com

일단 `paragraph = paragraph.lower()` 써서 소문자로 바꾸는 건 맞을거같고, 

그 다음에 일단 `paras = paragraph.split()` 써서 공백 기준으로 나누고,

그럼 저기엔 ['Bob', 'hit', ... ] 형태로 저장이 될거임.

 

이제 여기서 어떻게 하냐...

일단 각 리스트 요소 문자열에서 구두점 없애는 게 선행되어야 할듯?

	# maketrans()로 테이블 만들기
        table = str.maketrans('', '', string.punctuation)
        # translate()로 구두점 제거
        paragraph = paragraph.translate(table)

위 과정을 거치면, paragraph에는 구두점 제거된 문자열이 저장됨.

 

일단 딕셔너리로 하는 게 떠오르는데.

`dict = {}`로 빈 딕셔너리 하나 만들어놓고, `for word in paras` 해놓고 만약 `if word in dict: dict[word] += 1` `else: dict[word] = 1`(새로 등록)

공부내용

* `string.punctuation` 

모든 아스키 구두점 문자들을 포함하는 문자열

` !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~`

 

* 파이썬에서 문자열 내에 있는 구두점 제거하는법

- 여러 방법이 가능함. 

https://stackoverflow.com/questions/265960/best-way-to-strip-punctuation-from-a-string

 

`s.translate(str.maketrans('', '', string.punctuation))`

: 나는 s이라는 문자열에서 `아무 문자도 치환하지 않으며 구두점을 제거한다는 변환 규칙`에 따라 새로운 문자열을 생성하겠다.

이 문제에서는, 입력값이 크지 않아서인지 셋 다 `3ms`대로 같은 시간이 소요되었음.

* 일반적인 상황에서의 str.replace() vs re.sub (=정규 표현식) vs str.translate()

https://cuffyluv.tistory.com/121

 

[Python] 문자열 치환 메서드 성능 비교 - str.replace(), re.sub(), str.translate()

https://cuffyluv.tistory.com/120 [Python/leetcode] 819. Most Common Wordhttps://leetcode.com/problems/most-common-word/description/가장 흔한 단어.금지된 단어를 제외하고, 가장 흔하게 등장하는 단어를 출력해라. 대소문자

cuffyluv.tistory.com

윗 글 참고!! 명확하게 정리된 글이 없어 직접 정리해봤다.

* 파이썬에서 리스트 내 요소 개수 구하는 법

- 딕셔너리를 사용해 `key:value`에 `요소:빈도`를 저장할 수 있음.

- 이 때, dictionary의 indexing 및 assignment를 사용해 없으면 추가, 있으면 갱신이 가능.

		if word in word_count: 
                    word_count[word] += 1
                else:
                    word_count[word] = 1

* `max()` 함수와 key 사용법

- 리스트, 튜플, 또는 다른 반복 가능한 객체(iterable)에서 가장 큰 값을 찾을 때 사용합니다.

- key 인자는 최댓값을 비교할 때 사용할 기준을 지정합니다. key에는 함수나 람다식을 넣을 수 있습니다.

- https://cuffyluv.tistory.com/119 에서 공부한 sort의 key 매개변수와 동일한 원리.

* 파이썬의 Collections 모듈

- collections 모듈은 파이썬의 자료형(list, tuple, dict)들에게 확장된 기능을 주기 위해 제작된 파이썬의 내장 모듈이다.

- 자주 쓰는 클래스는 다음과 같다: `Counter`,`deque`,`defaultdict`

참고 : https://velog.io/@matt2550/%ED%8C%8C%EC%9D%B4%EC%8D%AC-Collections-%EB%AA%A8%EB%93%88-3%EC%A2%85-%EC%A0%95%EB%A6%AC

- collections.defaultdict()의 경우는, 예를 들어 int를 사용하면 기본값으로 0을 반환하고, list를 사용하면 기본값으로 빈 리스트 []를 반환함.

1차 풀이

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
	# 일단 소문자로 만들고
        paragraph = paragraph.lower()

        # maketrans()로 테이블 만들기
        table = str.maketrans('', '', string.punctuation)
        # translate()로 구두점 제거
        paragraph = paragraph.translate(table)

	# 공백 기준으로 리스트로 만들자
        para_list = paragraph.split()

        # 단어를 key, 빈도를 value로 가지는 딕셔너리 생성
        # banned에 포함된 단어는 딕셔너리에 넣지 않음.
        word_count = {}
        for word in para_list:
            if word not in banned:
                if word in word_count: 
                    word_count[word] += 1
                else:
                    word_count[word] = 1
            	# 위 4줄은 아래 코드 한 줄로 더 간결하게 구현 가능하다. 
		# word_count[word] = word_count.get(word, 0) + 1:

        # 가장 value가 큰 key를 찾기
        most_common_word = max(word_count, key = word_count.get)

        return most_common_word

48/49 테스트 케이스로 리젝됐다.

`"a, a, a, a, b,b,b,c, c"`에 `["a"]` 밴 됐을 때, `b`가 아닌 `bbbc`가 출력됐음... 나는 공백 기준으로만 나눠서 생긴 결과.

 

따라서, 나는 구두점을 제거하는 게 아닌, 구두점을 공백으로 대체하는 코드를 짜야 함 !!!!

str.translate() 치환 사용

     	for p in string.punctuation:
            table = str.maketrans(p, ' ')
            paragraph = paragraph.translate(table)

아까 코드의 line 6~9를 위와 같이 대체하면 간단히 Accepted됨.

속도는 7ms로 가장 떨어졌음.

str.translate() 치환 사용 개선버전

	# maketrans()로 테이블 만들기
        table = str.maketrans(string.punctuation, ' ' * len(string.punctuation))
        # translate()로 구두점 제거
        paragraph = paragraph.translate(table)

한 번에 매핑 테이블 정의.

속도는 3ms로 오름.

str.replace() 사용

	# replace를 사용해 구두점을 공백으로 대체.
        for c in string.punctuation:
            paragraph=paragraph.replace(c," ")

 

아까 코드의 line 6~9를 위와 같이 대체하면 간단히 Accepted됨.

속도는 3ms.

정규 표현식 사용

		# 정규 표현식 사용
        	paragraph = re.sub(r'[^\w]', ' ', paragraph)

마찬가지로 아까 코드의 line 6~9를 위와 같이 대체하면 간단히 Accepted됨.

https://wikidocs.net/4308

이거 보고 정규 표현식 공부하자.

속도는 3ms.

정규 표현식 + list comprehension

여기서, 정규 표현식과 list comprehension을 섞어 쓰면, 좀 더 간결하게 코딩이 가능함.

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        # 정규 표현식 및 list comprehension 사용
        para_list = [word for word in re.sub(r'[^\w]', ' ', paragraph)
            .lower().split() if word not in banned]

        # 단어를 key, 빈도를 value로 가지는 딕셔너리 생성
        # banned에 포함된 단어는 딕셔너리에 넣지 않음.
        word_count = {}
        for word in para_list:
            if word in word_count: 
                word_count[word] += 1
            else:
                word_count[word] = 1

        # 가장 value가 큰 key를 찾기
        most_common_word = max(word_count, key = word_count.get)

        return most_common_word

collections.defaultdict 사용

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        # 정규 표현식 및 list comprehension 사용
        para_list = [word for word in re.sub(r'[^\w]', ' ', paragraph)
            .lower().split() if word not in banned]

        # 단어를 key, 빈도를 value로 가지는 딕셔너리 생성
        word_count = collections.defaultdict(int)
        for word in para_list:
            word_count[word] += 1

        # 가장 value가 큰 key를 찾기
        most_common_word = max(word_count, key = word_count.get)
        return most_common_word

원래 dictionary는 없는 key를 조회하면 keyError가 발생하기 때문에, 우리는 if문으로 word가 word_list라는 dictionary에 key로 이미 존재하는지 존재안하는지를 나눠줘야 했다.

그러나, `collections.defaultdict()`를 사용하면, 없는 키가 조회될 때마다 해당 키를 기본값 value 0으로 dictionary에 추가해준다.

따라서, 우리는 그게 있든 없든 신경쓰지말고 그냥 조회해서 `+=1` 때리면 된다.

collections.Counter() 사용

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        # 정규 표현식 및 list comprehension 사용
        para_list = [word for word in re.sub(r'[^\w]', ' ', paragraph)
            .lower().split()
                if word not in banned]

        # 리스트 para_list의 각 요소의 빈도를 value로 가지는 dictionary를 생성.
        word_count = collections.Counter(para_list)
        return word_count.most_common(1)[0][0]

`collections.Counter()`을 사용해, 빈도를 value로 가지는 dictionary를 자동으로 생성할 수 있다.

이 때, `collections.Counter.most_common(1)`은 `빈도가 가장 높은 1개의 요소를 추출`해주고, 이는 `[('hat', 3)]` 꼴이기 때문에, indexing을 연속으로 2번 해줘서 `[0][0]` 리스트의 첫 요소(인 튜플)의 첫 번째 요소를 결과로 반환하여 끝나게 된다.

해당 글은 "파이썬 알고리즘 인터뷰(박상길)"을 공부한 내용과 책의 코드가 포함되어 있습니다.

https://github.com/onlybooks/python-algorithm-interview/tree/master

'Programming > 알고리즘 파이썬 문제풀이' 카테고리의 다른 글

[Python/LeetCode] 5. Longest Palindromic Substring  (0) 2025.01.29
[Python/LeetCode] 49. Group Anagrams  (0) 2025.01.28
[Python/LeetCode] 937. Reorder Data in Log Files  (0) 2025.01.21
[Python/LeetCode] 344. Reverse String  (0) 2025.01.21
[Python/LeetCode] 125. Valid Palindrome  (0) 2025.01.21

'Programming/알고리즘 파이썬 문제풀이' Related Articles

티스토리툴바