LeetCode 819번 문제

Park Choong Ho·2021년 10월 22일

1. 문제 이해

문제 조건을 보면

Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique.
The words in paragraph are case-insensitive and the answer should be returned in lowercase.

문자열과 금지할 단어 리스트가 들어오고 금지할 단어 리스트에 포함안된 단어중에서 문자열에서 가장 많이 나타난 단어를 반환한다. 문자열에는 금지안한 단어가 하나 무조건 포함되며 답인 단어도 하나밖에 없다.
그리고 문자열에 있는 단어들은 case-insensitive 하다. 정답은 소문자로 반환한다.

단어를 찾아야 하는 대상인 문자열(편의상 지금부터 단락이라 부름)에서 금지 단어 리스트에 있는 단어들 빼고 가장 빈도수가 높은 단어를 반환해야되는 문제입니다. 가장 빈도수가 높은 단어가 여러개인 경우가 있을 수 있으나 문제에서는 가장 빈도수가 높은 단어가 하나뿐이라며 제한사안을 걸어 두었습니다. 그리고 적어도 하나의 금지되지 않은 단어가 단락에 반드시 존재 한다고 합니다.

따라서,

금지되지 않은 단어 중 단락에서 가장 높은 빈도수를 보이는 단어는 하나이다.
적어도 하나의 금지되지 않은 단어가 단락에 반드시 존재한다.

이 조건들로 인해, 가장 높은 빈도수를 보이는 단어가 여러개여서 그중에서 단어를 선택하는 경우와 단락에 있는 모든 단어들이 단어 금지 리스트에 있어 단어를 셀 수 없는 경우는 고려하지 않습니다. 문제 이해는 여기까지 하고 다음으로 넘어가 보겠습니다.

2. 해결 계획의 작성

앞에서 말했던 문제의 2가지 조건

금지되지 않은 단어 중 단락에서 가장 높은 빈도수를 보이는 단어는 하나이다.

적어도 하나의 금지되지 않은 단어가 단락에 반드시 존재한다.

이 조건들로 인해 문제에서 생각해야되는 부분들이 줄어들었습니다. 이 문제는 그럼, 금지 문자열 리스트에 없는 단어들 갯수를 세서 그 중에서 가장 빈도수가 높은 단어를 반환하기만 하면 되는 문제입니다.

문제 조건을 다시 읽어보니 앞서 문제 이해에 있어 까먹은 조건이 있었습니다. 바로 문자열에 있는 단어들은 case-insesitive하며 정답은 소문자로 반환한다입니다.

만약 단락으로 Ball ball이 주어지고 금지 단어 리스트로 ["no"]가 주어졌다면 이 경우, ball이 2개가 있는 것이므로 ball로 반환해야 합니다. 그리고 추가적인 문제 조건을 보면

1 <= paragraph.length <= 1000

paragraph consists of English letters, space ' ', or one of the symbols: "!?',;.".

0 <= banned.length <= 100

1 <= banned[i].length <= 10

banned[i] consists of only lowercase English letters.

여기서 금지 단어 리스트는 항상 소문자 단어로 구성되어 있다는 것을 확인할 수 있습니다. 따라서 입력받은 단락을 소문자로 만들어서 금지 단어 리스트와 대조해서 가장 높은 빈도수를 보이는 단어를 반환한다. 로 계획을 세울 수 있습니다.

다만, 또 다른 문제가 있습니다. 바로 단락이 단순 영단어와 띄어쓰기만으로 구성된 것이 아니라, ! ? ' , ; .이 6가지 특수문자까지 포함한다고 되어있습니다. 따라서 이 문자들을 단락에서 제거해야 올바르게 단어들을 비교할 수 있습니다. 여기서는 정규 표현식을 사용해서 문제를 풀어보려고 합니다.

3. 계획의 실행

from re import sub

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

paragraph = paragraph.lower()
striped_paragraph = sub('[^a-z]', ' ', paragraph)

word_list = striped_paragraph.split()

word_dict = {}

for word in word_list:
    if word in banned:
        continue
    else:
        if word not in word_dict:
            word_dict[word] = 1
        else:
            word_dict[word] += 1
max_key = ''
max_value = 0
for key, value in word_dict.items():
    if value > max_value:
        max_value = value
        max_key = key

print(max_key)

다른 부분들은 이해하기 그렇게 어렵지 않으실거라 생각하고 여기서는 크게 2가지 부분을 살펴보았습니다.

정규 표현식

앞서 말했던 6가지 특수문자를 단락에서 제거하기 위해서 정규 표현식을 사용하도록 하겠습니다. 여기서 정규표현식의 전반적인 부분을 설명하면 글이 너무 길어질 것 같아 정규표현식은 가까운 시일에 한번 정리하도록 하겠습니다. 궁금하신 분들은 아래 위키를 들어가 보시기 바랍니다.

https://en.wikipedia.org/wiki/Regular_expression

정규 표현식을 사용하기 위해 re라는 파이썬 내장 모듈을 사용하겠습니다. 그 중에 sub이라는 함수를 사용합니다. sub 함수를 뜯어보면

Return the string obtained by replacing the leftmost non-overlapping occurrences of the pattern in string by the replacement repl. repl can be either a string or a callable; if a string, backslash escapes in it are processed. If it is a callable, it's passed the Match object and must return a replacement string to be used.

왼쪽에 있는 패턴을 repl로 변경한다는 의미입니다. striped_paragraph = sub('[^a-z]', ' ', paragraph) 에서 [^a-z]는 a부터 z가 아닌 문자를 의미합니다. 해당 단락에서는 소문자 알파벳을 제외한 특수 문자 6가지를 나타냅니다. 이들을 모두 공백으로 처리해서 단락에 온전히 알파벳 소문자로 구성된 단어들만 남을 수 있도록 했습니다.

dict.items()

문자열 갯수를 저장하기 위해서 파이썬 딕셔너리라는 자료구조를 사용했습니다. 여기서 dictionary.items() 라는 문법을 사용했습니다.

파이썬 공식문서를 보면

items()
Return a new view of the dictionary’s items ((key, value) pairs). See the documentation of view objects.

이라고 되어있고

The objects returned by dict.keys(), dict.values() and dict.items() are view objects. They provide a dynamic view on the dictionary’s entries, which means that when the dictionary changes, the view reflects these changes.

즉, dict.items()를 view object라고 하고 있습니다. dictionary entry에 들어가는 동적인 view를 제공하는 객체라고 하고 있습니다. 일단 dict.items()가 (key, value) 형태의 view object를 반환한다고 이해하면 될것 같습니다.

view object 관한 것은 아래 글을 참조하시면 좋을 것 같습니다.