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

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

 

 

코딩 테스트에서 점수를 받으려면, 주어진 문제를 에러 없이 주어진 시간 안에 정해진 정답을 출력해야 한다. 따라서 우리가 집중을 해야 할 부분은 첫째, 정답을 도출해 낼 수 있는 알고리즘을 짜야한다. 둘째, 주어진 시간 안에 코딩 정답을 도출해야 한다. 이러한 2가지 포인트에 집중하여, 아래의 글을 읽어주기 바란다.

 

 

 

문자열 유형

코딩 테스트에서 주로 1번 문제로 등장하는 문자열에 대해 정리해보고자 한다. 아래의 유형이 나오면 5분 안에 풀고 넘어가면 된다. 물론 아래의 유형으로 문자열을 요구사항에 맞게 정렬 후 다른 유형과 결합되어 나오기도 한다.

 

 

 

 

유형 1. 회문(Palindrome)

 회문, 즉 팰린드롬이란 앞뒤가 똑같은 단어나 문장을 의미한다. 이때 대소문자를 구분하지 않으며 글자와 숫자만 따지면 된다. ex_ '가나다다나가' 'Madam, I'm Adam'

 

문제로는 "앞뒤가 같은 단어를 찾아라.", "회문인 것을 찾아라." 등으로 출제되며, 최근 코딩 테스트는 영어로 코딩 테스트가 출제되고 있는데, "Palindrome"이라는 단어나 직접적으로 나올 수 있으니 단어도 눈에 익혀두길 바란다. 파이썬으로 이해해 보면 아래와 같다.

 

def isPalindrome(str):
    for i in range(len(str)//2):
        if str[i] == str[-i-1]:
            continue
        else:
            print('회문이 아닙니다.')
    print('회문입니다.')

data = 'abcba'
isPalindrome(data)

 

위의 예처럼 'abcba'과 같은 쉬운 회문은 쉽게 문제풀이가 가능하지만, 'Madam, I'm Adam'와 같이 대소문자나 특수기호가 포함되어 있다면, 회문을 판별하기 전에 'Madam, I'm Adam'에서 대문자와 특수기호를 제거하여, 'madamimadam'으로 변환해주는 전처리 과정을 진행해 준 후에 판별을 진행한다.

 

 

1단계

첫 번째 풀이로는 문자열 매서드인 isalnum()과 lower()을 활용하여 문자열을 리스트로 변환하여 문제를 풀어볼 것이다.

 

def inPalindrome(str):
    # 전처리
    list_str = []
    for char in str:
        if char.isalnum():
            list_str.append(char.lower())
            
    # 회문 판별
    while len(list_str) > 1:
        if list_str.pop(0) != list_str.pop():
            print('회문이 아닙니다.')
            return
    print('회문입니다.')

a = '0Madam, I\'m Adam0'
inPalindrome(a)

 

• isalnum()  :  영문자, 숫자 여부를 판별하여, 영문자와 숫자가 아니면 False를 리턴한다.
• lower()  :   영어 알파벳을 모두 소문자로 변환한다.
• pop()  :  리스트의 특정 인덱스의 요소를 잘라내서 가져온다.

사실 위의 풀이는 쉽다고 느껴질 풀이다. 왜냐하면, 모든 알고리즘 풀이에서 리스트를 사용하여 상대적으로 많이 쓰기 때문이다. 하지만, python에서 append(), pop()와 같이 리스트의 크기를 변경하는 함수들을 사용하면 굉장히 느려진다는 점을 초보단계에서는 일단 암기하고 넘어가자.

 

 

 

 

2단계

두 번째 풀이 단계는 슬라이싱이다. [::-1]로 풀면 된다. [::-1]은 슬라이싱으로 문자를 뒤집어준다. 따라서 '가나다다나가'를 회문인지를 판별하려면 아래와 같다.

 

s = ['가나다다나가']
if s == s[::-1]:
    print('회문이다')

 

여기서는 대문자와 특수기호, 띄어쓰기를 제거하는 전처리 과정을 정규식(re)을 사용하여 진행할 것이다. 먼저 아래의 코드를 보자.

 

import re
def inPalindrome(str):
    # 대문자를 소문자로 변경
    str = str.lower()
    
    # 정규식 사용
    str = re.sub('[^a-z0-9]', '', str)
    if str == str[::-1]:
        print('회문입니다')
    else:
        print('회문이 아닙니다')

a = '0Madam, I\'m Adam0'
inPalindrome(a)
'''
0madamimadam0
'''

 

 정규식에 대한 간단한 코드 설명을 하면 아래와 같다.

 

re.sub('패턴', '바꿀문자열', '적용할문자열')

ex_   print( re.sub('[0-9]+', 'n', '1 2 Fizz 4 Buzz Fizz 7 8') ) # 숫자만 찾아서 n으로 바꿈   '''   'n n Fizz n Buzz Fizz n n'   '''

 

정규식을 배우는 가장 큰 이유는 사실 웹 스크래핑으로 나아가는 단계에서 문자열을 쉽게 전 처리하기 위함이다. 초보자의 단계에서는 넘어가도 좋다. 간단한 이해를 위해서는 간단히 정규식 알아보기를 눌러서 확인하기 바란다.

 

 

 

3단계

파이썬에서 리스트에서 pop()를 이용해서 아래와 같이 리스트 안에 있는 1을 제거해 보자

 

list = [1, 2, 3, 4, 5]
list.pop()
print(list)
'''
[2, 3, 4, 5]
'''

 

1을 제거한 순간, 뒤의 2, 3, 4, 5가 앞으로 한칸씩 이동을 하기 때문에 리스트의 크기가 클수록 시간이 오래 걸린다. 따라서 코딩 테스트를 풀어야 하지만, 주어진 시간 안에 문제를 풀기가 어려운 경우가 있다. 따라서 우리는 deque를 사용한다. 

 

재귀를 배우게 된다면, 미로문제에서 BFS(너비 우선 탐색)를 구현하게 될 텐데 이때 Queue를 구현하기 위해서 반드시 deque를 사용한다. 현재 단계에서는 BFS, DFS니 알 필요는 없고, 리스트의 append와 pop 대신에 deque를 이용한다는 정도만 알아두자. 천천히 정리해서 하나씩 올려 보겠다. 코드를 보자.

 

import collections
def inPalindrome(str):
    deq = collections.deque()
    for char in str:
        if char.isalnum():
            deq.append(char.lower())
            
    # 회문 판별
    while len(deq) > 1:
        if deq.popleft() != deq.pop():
            print('회문이 아닙니다.')
            return
    print('회문입니다.')
a = '0Madam, I\'m Adam0'
inPalindrome(a)

 

deq의 사용법은 list와 비슷하다. append, pop를 동일하게 사용하면 된다. 다만, pop(0) 대신에 popleft()를 사용한다. pop(0)과 popleft의 성능을 비교하면, pop(0)은 전체 리스트의 원소를 하나씩 확인하여 찾는 반면에 popleft는 한 번에 찾기 때문에 빠르다.

 

 

마무리

회문문제란, 앞뒤가 같은 단어나 문장을 찾는 것이다. 위의 성능을 비교해 보면 아래와 같다.

 

풀이법	걸린시간(s)
1단계] 리스트변환	0.00041556358337402344s
2단계] 슬라이싱	0.00023317337036132812
3단계] deque	0.0002646446228027344

 

위의 표를 보면 역시나 슬라이싱을 활용하면 시간이 가장 적게 걸린다는 점을 알 수 있다.

 

---

 

유형 2. 문자열 뒤집기

이 유형은 리스트 내부에 있는 문자열을 뒤집는 방법을 물어보는 것이다. 예를 들면 ['a', 'b', 'c']를 ['c', 'b', 'a']로 변환하는 방식을 물어보는 것이다.

 

 

1단계

간단히 리스트에서 제공하는 reverse() 함수를 사용하면 된다.

 

def reverseString(str):
    str.reverse()
    print(str)

a = ['a', 'b', 'c', 'd', 'e']
reverseString(a)
'''
['e', 'd', 'c', 'b', 'a']
'''

 

 

2단계

우리는 위에서 [::1]라는 슬라이싱을 배웠다. 슬라이싱은 문자열뿐만 아니라, 리스트에서도 사용 가능하다.

 

a = 'abcde'
a = a[::-1]
print(a)
'''
edcba
'''

a = ['a', 'b', 'c', 'd', 'e']
a = a[::-1]
print(a)
'''
['a', 'b', 'c', 'd', 'e']
'''

 

만약 코딩 테스트 시에 `a=a[::-1]`가 오류가 뜬다면, 시스템 내부적으로 변수 할당에 제약을 걸어놨을 가능성이 있으므로 `a[:]=a[::-1]`로 변경하여 작성하자. 

 

 

3단계

투 포인터를 이용한 방법에 대해 알아보자. 아래의 코드처럼 처음과 끝은 인덱스를 변수로 지정한 후에 변수를 +1이나 -1 하여 인덱스를 이동시켜 조작하는 방식이다. 포인터를 활용한 방식은 나중에 정렬을 배울 때도 유용하게 사용되므로 이해하고 넘어가자.

 

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)

 

위의 코드에서 알 수 있듯이 첫번째 인덱스와 마지막 인덱스를 포인터(left_idx, right_dix)로 지정을 하고, 위치를 변경해 준다.

 

 

---

 

유형 3 조건에 맞게 재정렬

이 유형은 모르면 틀리는 유형이다. 아래의 간단한 data를 보자.

 

data = ['1 A', '1 B', '6 A', '2 D', '4 B']

 

리스트 안의 요소를 번호 순 정렬이 아닌 그 뒤의 문자 순으로 정렬해 보자. 이 유형은 풀이를 모르면 굉장히 시간이 오래 걸린다. 출제가 자주되니 암기하자.

 

1단계

함수로 풀면 아래와 같다. 핵심은 sort의 key인자이다.

 

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 A', '6 A', '1 B', '4 B', '2 D']

 

2단계

줄여서 짧게 나타내면 아래와 같다. (lambda)

 

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 A', '6 A', '1 B', '4 B', '2 D']

 

 

3단계

위의 유형은 DB관리 측면에서 굉장히 많이 출력된다. 예를 들면,  리스트 안에 회원의 아이디, 회원가입날짜, 사용자가 쓴 댓글들이 아래와 같이 구성되어 있다고 하자.

 

data = ["hanpy 20101213 재미없다 235 재미있다", ...]

 

문제는 이런식이다. 각각의 DB의 회원들을 댓글들 중에 숫자를 제거하고, 댓글들을 정렬한 후에, 가입한 날짜 순으로 재정렬하라. 이러한 문제가 나왔다면 어떻게 풀 것인지 생각해보자. 위의 방법을 모른다면 굉장히 복잡할 수 있는 문제지만, sort의 key를 적용한다면 쉽게 문제 풀이가 가능 할 것이다. 힌트를 주자면 아래와 같이 str과 int를 분리가능하다.

 

def divide_sentence(list_datas):
    str_l, int_l = [], []
    list_datas = list_datas.split()[2:]
    for data in list_datas:
        if data.isdigit():
            str_l.append(data)
        else:
            int_l.append(data)
        

 

• isalpha는 문자열이 문자인지를 판별하여 True, False를 알 수 있다.
• isdigit는 문자열이 숫자인지를 판별하여 True, False를 알 수 있다.

 

문자열 [코딩테스트] 문자열 유형 기초 정리_2 에서 다음 내용을 이어가겠다.