[코딩테스트] 문자열 유형 완벽 정리_2

아래의 내용은 파이썬 알고리즘 인터뷰 책을 참고하여 작성하였다.

 

이전 내용은 아래의 링크를 참고하자

문자열 유형 기초 정리_1

 

 

유형 4. 특정 단어 추출

> 이 유형은 NLP에서도 자주 사용되는 스킬이다.

 

paragraph = "Bob hit a ball, the hit BALL flew far after it was hit"

위의 예제에서 "hit"을 제외한 단어 중 가장 많이 등장하는 단어를 뽑는 코드를 작성하자. 대소문자는 구분하지 않고 구두점은 무시한다.

 

 

 

1단계

정규식을 사용해서 불필요한 구두점을 지우자

 

import re
re.sub('[^\w]', ' ', paragraph)

 

 [^\w] 은 모든 문자와 숫자를 제외하고는 공백으로 바꾼다.

 

 

 

2단계

정규식에 추가적으로 처리를 해보자. 

 

banned = 'hit'
word_list = re.sub('[^\w]', ' ', paragraph).lower().split()
words = [word for word in word_list if word not in banned]
print(words)
'''
['bob', 'a', 'ball', 'the', 'ball', 'flew', 'far', 'after', 'was']
'''

 

lower()는 소문자 변경을 해준 후에 split()를 사용해서 리스트로 만든 후에 금지어가 아닌 단어만, words 리스트에 담는다.

 

 

3단계

Counter() 함수를 사용해서 빈도수를 계산하자. Counter는 자연어 처리에서 자주 쓰인다. 관련 내용은 아래에 정리한다.

 

import collections
counts = collections.Counter(words)
print(counts)
'''
Counter({'a': 1,
         'after': 1,
         'ball': 2,
         'bob': 1,
         'far': 1,
         'flew': 1,
         'the': 1,
         'was': 1})
'''

print(counts.most_common()[0][0])
'''
ball
'''

 

위와 같이 ball이 나오는 것을 확인할 수 있다. 정리한 코드는 아래와 같다.

 

import re
import collections

banned = 'hit'
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit"
words = [word for word in re.sub('[^\w]', ' ', paragraph).lower().split() if word not in banned]
counts = collections.Counter(words)
counts.most_common()[0][0] # 답

 

 

---

Counter()에 대한 정리

> Counter 객체는 아이템에 대한 개수를 딕셔너리로 리턴하여 준다. 개수를 자동으로 계산해 주기 때문에 매우 편리하다. most_common()을 사용하면 빈도 수가 가장 높은 요소를 추출 가능하다. 아래의 예를 통해 이해해보자.

 

import collections
data = [1, 2, 3, 3, 4, 5, 6, 6, 6, 7, 8]
dic_data = collections.Counter(data)
print(dic_data)
```
Counter({6: 3, 3: 2, 1: 1, 2: 1, 4: 1, 5: 1, 7: 1, 8: 1})
```

print(type(dic_data))
```
<class 'collections.Counter'>
```

print(dic_data.most_common())
```
[(6, 3), (3, 2), (1, 1), (2, 1), (4, 1), (5, 1), (7, 1), (8, 1)]
```

print(dic_data.most_common(2))
```
[(6, 3), (3, 2)]
```

 

위의 예를 보면 most_common() 내부에 int를 넣으면, 빈도수가 높은 순으로 개수가 출력이 되는 것을 알 수 있다.. 빈도수라는 단어를 들으니 Bow(Bag-of-Words)가 생각난다. 자연어 처리에 Counter를 적용하면 아래와 같다.

 

# 자연어 처리의 예로 Counter를 이해해 보자.
from collections import Counter
sentences = [['barber', 'person'], ['barber', 'good', 'person'], ['barber', 'huge', 'person'], ['knew', 'secret'], ['secret', 'kept', 'huge', 'secret'], ['huge', 'secret'], ['barber', 'kept', 'word'], ['barber', 'kept', 'word'], ['barber', 'kept', 'secret'], ['keeping', 'keeping', 'huge', 'secret', 'driving', 'barber', 'crazy'], ['barber', 'went', 'huge', 'mountain']]



# 단어들을 하나의 리스트로 만들자
words = sum(sentences, [])
print(words)
'''
['barber', 'person', 'barber', 'good', 'person', 'barber', 'huge', 'person', 'knew', 'secret', 'secret', 'kept', 'huge', 'secret', 'huge', 'secret', 'barber', 'kept', 'word', 'barber', 'kept', 'word', 'barber', 'kept', 'secret', 'keeping', 'keeping', 'huge', 'secret', 'driving', 'barber', 'crazy', 'barber', 'went', 'huge', 'mountain']
'''


# 중복을 제거하고 빈도수를 기록하자.
vocab = Counter(words) # 파이썬의 Counter 모듈을 이용하면 단어의 모든 빈도를 쉽게 계산할 수 있다.
print(vocab)
'''
Counter({'barber': 8, 'secret': 6, 'huge': 5, 'kept': 4, 'person': 3, 'word': 2, 'keeping': 2, 'good': 1, 'knew': 1, 'driving': 1, 'crazy': 1, 'went': 1, 'mountain': 1})

빈도수를 리턴하려면 아래와 같다.
print(vocab["barber"]) # 'barber'라는 단어의 빈도수 출력
> 8
'''
# most_common()는 상위 빈도수를 가진 주어진 수의 단어만을 리턴
vocab_size = 5
vocab = vocab.most_common(vocab_size) # 등장 빈도수가 높은 상위 5개의 단어만 저장
vocab
'''
[('barber', 8), ('secret', 6), ('huge', 5), ('kept', 4), ('person', 3)]
'''

# 높은 빈도수 => 낮은 정수 인덱스
word_to_index = {}
i = 0
for (word, frequency) in vocab :
    i = i+1
    word_to_index[word] = i
print(word_to_index)
'''
{'barber': 1, 'secret': 2, 'huge': 3, 'kept': 4, 'person': 5}
'''

 

 

 

---

 

 

유형 5. 애너그램(anagrams)

> 애너그램이란 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말한다. 아래와 같이 입력값을 넣었을 때, 알파벳 순서를 바꾸면 같은 값이 되는 것들끼리 묶어서 출력되는 알고리즘을 작성해 보자. (출력 값에서 그룹의 순서는 정답에 영향을 끼치지 않는다.)

 

입력값 : ["eat","tea","tan","ate","nat","bat"]
출력값 : [["bat"],["nat","tan"],["ate","eat","tea"]]

 

잠시 풀이 방법을 생각해 보자. 

 

 

 

풀이는 간단하다. 각각의 단어를 sorted()한 값들을 비교하여 같은 단어끼리 묶어주면 된다. 풀이는 다음과 같다.

 

import collections
data = ["eat","tea","tan","ate","nat","bat"]
sort_data = collections.defaultdict(list)
for word in data:
    sort_data[''.join(sorted(word))].append(word)
print(sort_data.values())

 

sort_data = collections.defaultdict(list)에서 defaultdict에 관한 설명은 여기를 눌러서 확인하고 오자.

 

sort_data [''. join(sorted(word))]. append(word)

• word에 sorted를 하고 join을 붙여주는 이유는 sorted()의 결과 값은 리스트가 되기 때문이다. 따라서 'eat'가  sorted()를 만나면 ['a', 'e', 't'] 출력된다. 따라서 join을 활용하여 'aet'로 바꿔준다고 생각하면 된다.
• 뒤에 append를 한 이유는 sort_data [''. join(sorted(word))]의 결과 값이 리스트기 때문에, 리스트에 값을 넣어주기 위해 append를 활용한 것이다.

sorted()와 sort()의 차이는 여기를 눌러서 확인하자.

 

 

 

---

 

 

유형 6. 가장 긴 팰린드롬 찾기

> 주어진 문자열에 존재하는 많은 팰린드롬 중에 가장 긴 팰린드롬을 찾는 방법을 생각해 보자. 앞에서 우리는 [::-1]을 통해 팰린드롬을 찾아본 적이 있다. 기억이 안 난다면 문자열 기초정리_1을 다시 보고 오자.

 

인덱스를 0부터 끝까지 하나씩 위치를 이동해가면서 팰린드롬을 확인하는 방법이 최선이다. 코드로 확인해보자.

 

def palindrome(n, left, right):
    while right <= len(data) and left >= 0 and data[left] == data[right-1]:
        right += 1
        left -= 1
    return data[left + 1 : right -1]

data = 'ewqpbewqbfjabcdefedcbaienqnfkndkl'
# data = 'abbc'
res = ''
if data == data[::-1] or len(data) < 2:
    print(data)
else:
    for i in range(len(data)-1):
        res = max(res, palindrome(len(data), i, i+1), palindrome(len(data), i, i+2), key=len)
    print(res)

'''
abcdefedcba
'''

 

위의 코드는 굉장히 헷갈린다. 왜냐하면 포인터를 이동하면서 검사를 하는데, 머리로 생각하기가 어렵기 때문이다. 반드시 연습장에 적으면서 풀어보자. 이 정도 이해가 된다면, 두 포인터 문제는 어느 정도 완성했다고 생각해도 좋다. 어려운 내용이니 시간을 가지고 천천히 생각해보자. (노트에 적어가면서 하나씩 움직이면서 이해하자. 눈으로 이해한다면 천재다.)

 

 

코드 설명은 아래와 같다.

 

 

if data == data [::-1] or len(data) < 2:

- 위에서 작성한 코드는 순차적으로 인덱스 0부터 팰린드롬을 검사한다. 따라서 data==data [::-1]인 경우 굳이 처음부터 검사를 할 필요가 없기 때문에 제거한다고 할 수 있다. 이렇게 불필요한 계산을 하지 않게 하는 것을 가지치기라 한다. 코드가 뻗어나가기 전에 가지를 쳐서 잘라낸다고 생각을 하자. (앞으로 나갈 완전 탐색에서 필수적인 스킬이다.)

 

 

 

res = max(res, palindrome(len(data), i, i+1), palindrome(len(data), i, i+2), key=len)

- 이 부분을 보면, max안에 key인자가 들어있는 것을 알 수 있다. key=len의 의미는 내용 중에 길이가 가장 긴 값을 리턴한다는 의미이다. 즉, for문을 반복하면서, max를 활용하여 길이가 가장 긴 값을 res에 담은 후, 다시 res 변수를 max에 넣는 것을 반복하여 모든 팰린드롬의 경우 중에 가장 긴 팰린드롬을 찾는 것이다.

 

 

 

 

추가적으로 관련 내용을 계속 업데이트할 예정이다. 문자열 끝-