문자열 유형
코딩 테스트에 등장하는 문자열 유형에 대해 정리한 내용이다.
유형1. 회문(Palindrome)
앞뒤가 똑같은 단어나 문장을 의미한다. 대소문자를 구분하지 않는다.
1
2
3
4
5
6
7
8
9
10
def Palinedrome(str):
for i in range(len(str) // 2):
if str[i] == str[-i-1]:
continue
else:
print('회문이 아닙니다.')
print('회문입니다.')
data = 'abcba'
Palinedrome(data)
1
회문입니다.
- 위 방법은 대소문자나 특수기호가 포함되어 있다면, 전처리 과정이 필요하다.
isalnum()과lower()을 활용하여 문자열을 리스트로 변환
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def Palinedrome(str):
# Preprocessing
list_str = []
for char in str:
if char.isalnum(): # 영문자, 숫자 여부 판별하여 아니면 False를 return
list_str.append(char.lower())
# 회문 판별
while len(list_str) > 1:
if list_str.pop(0) != list_str.pop():
print('회문이 아닙니다.')
return
print('회문입니다.')
data = '0Madam, I\'m Adam0'
Palinedrome(data)
1
회문입니다.
- 두 번째 단게는 슬라이싱이다.
[::-1]은 슬라이싱으로 문자를 뒤집어준다.- 정규표현식
1
re.sub('패턴', '바꿀 문자열', '적용할 문자열')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import re
def Palinedrome(str):
# 대문자 -> 소문자
str = str.lower()
# 정규표현식
str = re.sub('[^a-z0-9]', '', str)
print(str)
if str == str[::-1]:
print('회문입니다.')
else:
print('회문이 아닙니다.')
data = '0Madam, I\'m Adam0'
Palinedrome(data)
1
2
0madamimadam0
회문입니다.
deque를 이용한다.재귀를 배우게 된다면, 미로 문제에서BFS(너비 우선 탐색)를 구현하게 될 때Queue를 구현하기 위해서 반드시deque를 사용한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import deque
def Palinedrome(str):
q = deque()
for char in str:
if char.isalnum():
q.append(char.lower())
# 회문 판별
while len(q) > 1:
if q.popleft() != q.pop():
print('회문이 아닙니다.')
return
print('회문입니다.')
data = '0Madam, I\'m Adam0'
Palinedrome(data)
1
회문입니다.
유형2. 문자열 뒤집기
- 리스트에서 제공하는
reverse()함수를 사용한다.
1
2
3
4
5
6
def reverseString(str):
str.reverse()
print(str)
a = ['a' , 'b', 'c', 'd', 'e']
reverseString(a)
1
['e', 'd', 'c', 'b', 'a']
- 슬라이싱
- 만약 코딩테스트 시에
a = a[::-1]에 오류가 발생한다면, 시스템 내부적으로 변수 할당에 제약을 걸어놨을 가능성이 있으므로a[:] = a[::-1]로 변경하여 사용한다.
1
2
3
4
5
6
7
a = 'abcde'
a = a[::-1]
print(a)
a = ['a' , 'b', 'c', 'd', 'e']
a = a[::-1]
print(a)
1
2
edcba
['e', 'd', 'c', 'b', 'a']
투 포인터를 이용한 방법이다.- 처음과 끝 인덱스를 변수로 지정한 후 변수를
+1이나-1하여 인덱스를 이동시켜 조작하는 방식이다. - 해당 방식은
정렬에서 유용하게 사용된다.
1
2
3
4
5
6
7
8
9
10
def reverseString(str):
left_idx, right_idx = 0, len(str) - 1
while left_idx < right_idx:
str[left_idx], str[right_idx] = str[right_idx], str[left_idx]
left_idx += 1
right_idx -= 1
print(str)
a = ['a', 'b', 'c', 'd', 'e']
reverseString(a)
1
['e', 'd', 'c', 'b', 'a']
유형3. 조건에 맞게 재정렬 ★★★
- 해당 유형은 모르면 틀리는 유형이다.
- 핵심은
sort의key인자이다.
1
2
3
4
5
6
7
data = ['1 A', '1 B', '6 A', '2 D', '4 B']
def func(x):
return x.split()[1], x.split()[0]
data.sort(key=func)
print(data)
1
['1 A', '6 A', '1 B', '4 B', '2 D']
- 위 내용을 줄여서 짧게 나타내면 다음과 같다.
lambda를 사용한다.
1
2
3
4
data = ['1 A', '1 B', '6 A', '2 D', '4 B']
data.sort(key=lambda x: (x.split()[1], x.split()[0]))
print(data)
1
['1 A', '6 A', '1 B', '4 B', '2 D']
유형4. 특정 단어 추출
NLP에서도 자주 사용되는 스킬이다.- hit을 제외한 단어 중 가장 많이 등장하는 단어를 뽑는 코드를 작성한다. 대소문자는 구분하지 않고, 구두점은 무시한다.
1
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit"
정규표현식을 사용하여 불필요한 구두점을 지운다.
1
2
3
4
5
6
7
import re
banned = 'hit'
word_list = re.sub('[^\w]', ' ', paragraph).lower().split()
words = [word for word in word_list if word not in banned]
print(words)
1
['bob', 'a', 'ball', 'the', 'ball', 'flew', 'far', 'after', 'was']
Counter()함수를 사용해빈도수를 계산한다.- 자연어 처리에서 자주 쓰인다.
1
2
3
from collections import Counter
counts = Counter(words)
print(counts)
1
Counter({'ball': 2, 'bob': 1, 'a': 1, 'the': 1, 'flew': 1, 'far': 1, 'after': 1, 'was': 1})
Counter()객체는 아이템에 대한 개수를딕셔너리로 리턴해준다.most_common()을 사용하면 빈도수가 가장 높은 요소를 추출 가능하다.
1
2
3
4
5
6
7
import collections
data = [1, 2, 3, 3, 4, 5, 6, 6, 6, 7, 8]
dic_data = Counter(data)
print(dic_data)
print(dic_data.most_common())
1
2
Counter({6: 3, 3: 2, 1: 1, 2: 1, 4: 1, 5: 1, 7: 1, 8: 1})
[(6, 3), (3, 2), (1, 1), (2, 1), (4, 1), (5, 1), (7, 1), (8, 1)]