문자열 조작이란 문자열을 변경하거나 분리하는 등의 여러 과정을 말한다. 대부분의 언어에서는 별도의 문자열 자료형과 문자열을 조작하기 위한 다양한 기능들을 기본적으로 제공하고 있기 때문에, 굳이 제약을 두지 않는 한, 언어에서 제공하는 기본 기능들을 잘 활용하는 편이 가장 좋다.
문자열 조작은 코딩테스트에서 매우 빈번하게 출제되는 주제 중 하나며, 특히 실무에서도 다양한 분야에 쓰이는 상당히 실용적인 주제다. 문자열 처리와 관련된 알고리즘이 쓰이는 대표적인 분야는 다음과 같다.

• 정보 처리 분야: 어떤 키워드로 웹 페이지를 탐색할 때 문자열 처리 애플리케이션을 이용하게 된다. 특히 현대의 모든 정보는 문자열로 구성되어 있으며 문자열 처리는 정보 처리에 핵심적인 역할을 한다.
• 통신 시스템 분야: 문자 메시지나 이메일을 보낼 때 기본적으로 문자열을 어느 한 곳에서 다른 곳으로 보내게 된다. 이처럼 데이터 전송은 문자열 처리 알고리즘이 탄생한 기원이기도 하며, 데이터 전송에서 문자열 처리는 매우 중요한 역할을 한다.
• 프로그래밍 시스템 분야: 프로그램은 그 자체가 문자열로 구성되어 있다. 컴파일러나 인터프리터 등은 문자열을 해석하고 처리하여 기계어로 변환되는 역할을 하며, 여기에는 매우 정교한 문자열 처리 알고리즘 등이 쓰인다.

앞에 3장에서는 문제 풀이를 위한 다양한 자료형과 사전 지식 등을 살펴봤다. 이제부터는 문자열과 관련된 문제를 본격적으로 풀이해보면서, 파이썬의 문자열 자료형에는 어떠한 기능들이 제공되고 문자열 조작과 처리에 어떠한 기법들이 쓰이는지 하나씩 살펴본다.

문제1

주어진 문자열이 펠린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

풀이1

1. 대소문자 여부를 구분하지 않는다는 것, 영문자와 숫자만을 대상으로 한다는 것. 이 부분에 대한 처리를 한다.

str = []
for x in text:
    if x.isalnum():
        str.append(x.lower())

여기서 isalnum()는 영문자, 숫자 여부를 판별하는 함수로, 이를 이용해 해당하는 문자만 추가한다. 또한 lower()은 대문자를 소문자로 변환하는 역할을 한다. 이를 통해 새로운 리스트를 생성하고 영문자(소문자)와 숫자만이 리스트의 원소가 된다.

2. 팰린드롬 여부 판별

while len(str) > 1:
    if str.pop(0) != str.pop():
        return False

pop()은 리스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제한다. 파이썬의 리스트는 pop()함수에서 인덱스를 지정할 수 있기 때문에, 이처럼 0지정하면 맨 앞 값을 가져올 수 있다. 이렇게 맨 뒷부분의 pop() 결과와 매칭해 나가면서 일치하지 않는 경우 False를 리턴한다. 모두 통과했다면 True를 리턴한다.

전체코드는 아래와 같다.

def palindrome(self, text: str) -> bool:
    str = []
    for x in text:
        if x.isalnum():
            str.append(x.lower())
    #팰린드롬 여부 판별
    while len(str) > 1:
        if str.pop(0) != str.pop():
            return False
    return True

풀이2

이처럼 리스트만으로도 충분히 문제를 해결할 수 있지만 데크(Deque)를 명시적으로 선언하면 좀 더 속도를 높일 수 있다. 앞서 수행한 풀이는 좋은 풀이라고는 할 수 없는데 (평균 속도가 304밀리초) 간단히 데크로 변경하는 것만으로 얼마나 개선됐는지 살펴보자.

보통 큐(queue)는 선입선출(FIFO) 방식으로 작동한다. 반면, 양방향 큐가 있는데 그것이 바로 데크(deque)다.
즉, 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.
데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.
컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.

def palindrome2(text: str) -> bool:
    #자료형 데크로 선언
    str = collections.deque()
    for x in text:
        if x.isalnum():
            str.append(x.lower())

    while len(str) > 1:
        if str.popleft() != str.pop():
            return False
    return True

여기서 자료형을 데크로 선언하는 것만으로 64밀리초에 실행됐다. 앞서 풀이1에 비해 거의 5배 가까이 속도를 높일 수 있었다. 이는 리스트의 pop(0)이 O(n)인 데 반해, 데크의 popleft()는 O(1)이기 때문이다. 각각 n번씩 반복하면 리스트 구현은 O(n^2), 데크 구현은 O(n)으로 성능차이가 크다. 어쨌든 이 정도 성능이면 나쁘지 않다. 하지만 파이썬의 본격화된 내부 기능을 잘 활용해 성능을 좀 더 높여보자.

풀이3

import re
def palindrome3(text: str) -> bool:
    str = text.lower()
    #정규식으로 불필요한 문자 필터링
    str = re.sub('[^a-z0-9]', '', str)
    return str == str[::-1]

re.sub（정규 표현식, 대상 문자열 , 치환 문자）
정규 표현식 - 검색 패턴을 지정
대상 문자열 - 검색 대상이 되는 문자열
치환 문자 - 변경하고 싶은 문자

여기에서는 별달리 알고리즘이라 부를 만한게 없다. 정규식으로 불필요한 문자를 필터링하고, 문자열을 조작할 수 있는 파이썬의 슬라이싱을 사용했다. 앞서 풀이에서는 isalnum()으로 모든 문자를 일일이 점검했다.
여기서는 문자열 전체를 한 번에 영숫자만 걸러내도록 정규식으로 처리했다. 또한 파이썬은 문자열을 배열이나 리스트처럼 자유롭게 슬라이싱할 수 있는 좋은 기능을 제공하며, [::-1]을 이용하면 뒤집을 수 있다. 코드가 훨씬 더 줄어듦은 물론, 내부적으로 빠르게 구현되어 있어 훨씬 더 좋은 속도를 기대할 수 있다. 이 경우 실행속도는 36밀리초로, 앞선 두번째 풀이에 비해 약 2배 정도 더 속도를 높일 수 있다.

※ 문자열 슬라이싱
파이썬에서는 문자열 슬라이싱이라는 매우 편리한 기능을 제공한다. 무엇보다 내부적으로 매우 빠르게 동작한다. 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 찾아내는데, 이 과정은 매우 빠르게 진행되므로 문자열을 조작할 때는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리하다. 문자열을 별도로 리스트로 매핑하는 등의 처리는 데이터 구조를 다루는 입장에서는 좋은 방법이지만, 별도 자료형으로 매핑하는 과정에서 상당한 연산 비용이 필요하므로 전체적인 속도에서는 오히려 손해를 볼 수 있다. 대부분의 문자열 작업은 슬라이싱으로 처리하는 편이 가장 빠르다.

문제2

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

• 입력
  paragraph = "Bob hit a ball, the hit BALL flew far after it was hit"
  banned = ["hit"]
• 출력
  "ball"

입력값에는 대소문자가 섞여 있으며 쉼표 등 구두점이 존재한다. 따라서 입력값에 대한 전처리 작업이 필요하다. 좀 더 편리하게 처리하기 위해 정규식을 섞어 쓰면 다음과 같이 처리할 수 있다.

paragraph = "hi nice to meet you"
banned = ["hit"]
words = [word for word in re.sub(r'[^\w]', ' ', paragraph)
            .lower().split() 
                if word not in banned]

정규식에서 \w는 단어 문자를 뜻하며, ^은 not을 뜻한다. 따라서 위 정규식은 단어 문자가 아닌 모든 문자를 공백으로 치환하는 역할을 한다.
아울러 리스트 컴프리헨션의 조건절에는 banned에 포함되지 않은 단어만을 대상으로 한다. 따라서 words에는 소문자, 구두점을 제외하고 banned를 제외한 단어 목록이 저장된다. 이제 다음과 같이 각 단어의 개수를 헤아려 보자.

counts = collections.defaultdict(int)
for word in words:
    counts[word] += 1

collections.defaultdict는 딕셔너리(dictionary)와 거의 비슷하지만 key값이 없을 경우 미리 지정해 놓은 초기(default)값을 반환하는 dictionary이다.

여기서 개수를 담아두는 변수는 딕셔너리를 사용하며 defaultdict()를 사용해 int 기본값이 자동으로 부여되게 했다. 따라서 여기서는 키 존재 유무를 확인할 필요 없이 즉시 counts[word] += 1 을 수행할 수 있다.

return max(counts, key = counts.get)

딕셔너리 변수인 counts에서 값이 가장 큰 키를 가져온다.

문제3

문자열 배열을 받아 애너그램 단위로 그룹핑하라.

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

※여러 가지 정렬 방법

파이썬은 기본 정렬 함수를 기본으로 제공한다. 다음은 sorted() 함수를 이용한 파이썬 리스트를 정려하는 예다.

a = [4,1,5,2,7,3]
print(sorted(a))

출력: [1, 2, 3, 4, 5, 7]

당연하게도 이처럼 리스트를 잘 정렬하며, 숫자뿐만 아니라 문자도 정렬이 가능하다.

b = 'akgbeug'
print(sorted(b))

출력: ['a', 'b', 'e', 'g', 'g', 'k', 'u']

문자열을 알파벳 순서대로 정렬한 리스트를 결과로 리턴한다. 다시 문자열로 결합하려면 다음과 같이 join()을 이용할 수 있다.

b = 'akgbeug'
print(''.join(sorted(b)))

출력: abeggku

sorted()라는 별도 함수 외에도 리스트 자료형은 sort() 메소드를 함께 제공하며, 리스트 자체를 정렬할 수 있다. 이를 제자리 정렬 이라고 부르는데, 일반적으로 제자리 정렬 알고리즘은 입력을 출력으로 덮어 쓰기 때문에 별도의 추가 공간이 필요하지 않으며, 리턴값이 없다. 따라서 정렬 결과를 별도로 리턴하는 sorted()와 다르므로 주의가 필요하다.

c = [4,2,5,7,1,3]
print(c.sort())
print(c)


출력: 
None
[1, 2, 3, 4, 5, 7]

sorted()는 또한 key = 옵션을 지정해 정렬을 위한 키 또는 함수를 별도로 지정할 수 있다. 다음 코드는 정렬을 위한 함수로 길이를 구하는 len을 지정한 경우이다.

list1 = ['ccc','aaaa', 'd', 'bb']
print(sorted(list1, key=len))

출력: ['d', 'bb', 'ccc', 'aaaa']

이 경우 문자열의 알파벳 순서가 아닌 길이 순서로 정렬된다.

함수를 이용해 키를 정의하는 방법을 좀 더 알아보자. 다음은 함수를 이용해 첫 문자열(s[0])과 마지막 문자열(s[-1])순으로 정렬하도록 지정했다.

list2 = ['cde', 'cfc', 'abc']
def fn(s):
    return s[0],s[-1]

print(sorted(list2, key=fn))

출력: ['abc', 'cfc', 'cde']

만약 그냥 sorted()로 처리했다면 c가 동일하고, 따라서 그 다음 문자열인 d와 f를 비교해 순서대로인 ['abc', 'cde', 'cfc'] 순으로 출력될 것 이다. 그러나 여기에는 두 번째 키로 마지막 문자열을 보게 했기 때문에, e와 c를 비교해서 ['abc', 'cfc', 'cde'] 순으로 출력된다.
.
.
다시 문제로 돌아가서
.
.

애너그램을 판단하는 가장 간단한 방법은 정렬하여 비교하는 것이다. 애너그램 관계인 단어들을 정렬하면, 서로 같은 값을 갖게 되기 때문이다. sorted()는 문자열도 잘 정렬하며 결과를 리스트 형태로 리턴하는데, 이를 다시 키로 사용하기 위해 join()으로 합쳐 이 값을 키로 하는 딕셔너리로 구성한다. 애너그램끼리는 같은 키를 갖게 되고 따라서 여기에 append()하는 형태가 된다.
이처럼 정렬한 값을 키로 하여 딕셔너리에 추가한다. 만약 존재하지 않는 키를 삽입할 경우 KeyError가 발생하므로, 에러가 나지 않도록 다음과 같이 항상 디폴트를 생성해주는 defaultdict()로 선언하며, 매번 키 존재 여부를 체크하지 않고 비교 구문을 생략해 간결하게 구성한다.

anagrams = collections.defaultdict(list)

모두 정리하면 다음과 같이 간단하게 풀이가 가능하다.

def groupAnagrams(strs:List[str])-> List[List[str]]:
    anagrams = collections.defaultdict(list)

    for word in strs:
        #정렬하여 딕셔너리에 추가
        anagrams[''.join(sorted(word))].append(word)
    return anagrams.values()