문자열 조작

이전 글에 이어서 파이썬 알고리즘 풀이에서 가장 많이 등장하는 로직 중 하나인 문자열 조작에 대해 더 알아보았다.

LeetCode 819.Most Common Word

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

Solution 1 리스트 컴프리헨션, Counter 객체 사용

입력값에는 대소문자가 섞여 있고 쉼표 등의 구두점이 존재한다. 이를 우선적으로 제거하는 데이터 클렌징이라는 전처리 작업을 해야한다. 좀 더 편리하게 처리하기 위해 정규식을 섞어 처리하였다.

words=[word for word in re.sub(r'[^\w]', ' ', paragraph).lower().split() if word not in banned]

정규식에서 \w는 단어 문자를 의미하고, ^는 not을 의미한다. 이는 단어 문자가 아닌 것들은 ' ', 즉 공백으로 치환하는 연산을 수행한다. split() 덕에 공백을 지준으로 각 단어들이 배열의 원소로 들어가게 되고 collections의 Counter 객체를 사용하여 각 원소들이 몇개 존재하는지에 대한 딕셔너리로 저장된다. most_common(1)[0][0]은 가장 흔하게 등장하는 단어의 첫번째 인덱스를 반환하게 된다.

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        words=[word for word in re.sub(r'[^\w]', ' ', paragraph).lower().split() if word not in banned]
        counts = collections.Counter(words)
        return counts.most_common(1)[0][0]

LeetCode 49.Group Anagrams

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

Solution 1 정렬하여 딕셔너리에 추가

가장 간단한 방법은 정렬하여 비교하는 것이다. 애너그램 관계인 단어들을 정렬하면 모두 같은 값을 가지게 된다. 정렬하여 비교한 뒤에 ''.join()을 통해 합쳐 이 배열을 딕셔너리의 value로 사용하는 방식이다. 존재하지 않는 키에 삽입할 때에 에러가 발생하지 않도록 collections.defaultdict()를 사용해준다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = collections.defaultdict(list)
        for word in strs:
            anagrams[''.join(sorted(word))].append(word)
        return list(anagrams.values())

여러가지 정렬방법

파이썬은 정렬함수를 기본적으로 제공한다. 이번에는 간단하게만 정렬에 대해서 알아보았다. 정렬의 방법에는 sorted()와 sort() 이렇게 두가지 방법이 있다.

a=[2, 4, 3, 1, 5]
sorted(a) # [1, 2, 3, 4, 5]
b=zbdaf
sorted(b) # ['a', 'b','d', 'f', 'z']

위와 같이 숫자 뿐만 아니라 문자도 매우 간단하게 정렬할 수 있다. 문자열 zbdaf를 정렬하면 리스트 형태로 반환된다. 다시 문자열로 결합하고 싶다면 다음과 같이 join()을 사용할 수 있다.

b=zbdaf
"".join(sorted(b)) # ['a', 'b','d', 'f', 'z']

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

alist.sort() # sort()는 리스트 자체를 제자리 정렬
alist = blist.sort() # 잘못된 구문. sort() 함수는 None을 리턴하므로 주의해야함

sorted()는 key= 옵션을 지정하여 정렬을 위한 키 또는 함수를 별도로 지정할 수 있다.

c=['ccc', 'aaaa', 'd', 'bb']
sorted(c, key=len) # ['d', 'bb', 'ccc', 'aaaa']

key에 len을 넣어주면 문자열의 길이 순서로 정렬을 해준다. 함수를 이용하여 정렬의 옵션을 지정할 수도 있다.

a=['cde', 'cfc', 'abc']
def fn(s):
	return s[0], s[-1]
print(sorted(a, key=fn) # ['abc', 'cfc', 'cde']

만약 key에 함수를 넣지 않고 그냥 sorted()를 사용했다면 ['abc', 'cde', 'cfc']의 순으로 정렬이 되었을 것이다. 그러나 fn 함수에서 첫번째로 가장 앞의 문자, 두번째로 가장 뒤의 문자를 확인하게 했기 때문에 cfc와 cde 중 가장 뒤의 문자가 c가 더 빠르기 때문에 ['abc', 'cfc', 'cde'] 이러한 순서로 정렬이 되었다. 람다를 사용하면 함수 정의 없이도 사용이 가능하다.

a=['cde', 'cfc', 'abc']
print(sorted(a, key=lambda s: (s[0], s[-1])) # ['abc', 'cfc', 'cde']

LeetCode 5.Longest Palindrome Substring

가장 긴 팰린드롬 부분 문자열을 출력하라.

Solution 1 중앙을 중심으로 확장하는 풀이

이는 다이나믹 프로그래밍으로 풀 수 있는 전형적인 문제이지만 다이나믹 프로그래밍을 이용한 풀이는 직관적으로 이해가 어렵고, 일반적인 예상보다 실행 속도가 늦기 때문에 여기서는 좀 더 직관적이면서도 훨씬 더 성능이 좋은 투 포인터가 중앙을 중심으로 확장하는 형태로 풀이해보려고 한다. 중앙에서부터 두개의 포인터가 양쪽으로 확장해가며 문자열 슬라이싱을 통해 팰린드롬의 여부를 확인한다. aba의 경우와 bb의 경우 모두 팰린드롬 이므로 좌 우의 간격을 1로 두고 실행하고 2로도 두고 실행하여 모든 경우를 확인한다. 이 중 max()함수에 key=len을 사용하여 길이가 가장 긴 결과값을 결과로 취하게 된다.

슬라이싱을 사용할 때에는 s=12345일 때, s[1:3]은 23이지만 s[3]은 4이다. 이와 같이 헷갈릴 수 있으므로 주의하며 풀이하는 것이 중요하다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left:int, right:int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left-=1
                right+=1
            return s[left+1:right]
        if len(s) < 2 or s == s[::-1]:
            return s
        result = ''
        for i in range(len(s)-1):
            result = max(result, expand(i, i+1), expand(i, i+2), key=len)
        return result

유니코드와 UTF-8

초기에 문자를 표현하던 방식은 ASCII 인코딩 방식으로 1byte에 모든 문자를 표현하였다. 이 중 1bit는 checksum으로 사용되었고 남은 7bit(128글자)로 문자를 표현했다. 이러한 방식은 한글이나 한자같은 문자는 2개 이상의 특수 문자를 합쳐서 표현하였는데 이 방식은 경우에 따라서 깨지거나 제대로 표현되지 않았다. 이러한 문제를 해결하기 위해 2~4byte의 여유로운 공간에 문자를 할당하는 유니코드가 등장하였다. 그러나 유니코드는 1byte로 표현 가능한 영문자도 2byte 이상의 공간을 사용하여 표현하였기 때문에 메모리 낭비가 발생하였다. 가변길이로 표현하는 방식이 필요하게 되었고 이가 바로 UTF-8이다.

파이썬2 이전에는 한글을 비롯한 특수 문자들이 모두 별도로 인코딩되는 구조였기 때문에 콘솔에서 원래 값을 제대로 출력하기 어려웠다. 파이썬3부터는 문자열을 모두 유니코드 기반으로 전환하였고 이 덕에 영어, 한글, 한자 등의 다국어를 출력하는데에 문제가 없어졌다.

Python이라는 문자열이 있다고 가정해보자. 만약 모든 문자를 4byte로 표현한다면 Python은 24byte가 필요하게 된다. 이 문자열은 ASCII코드로도 충분히 표현 가능하고 ASCII코드는 하나의 문자를 1byte로 표현하기 때문에 문자당 3byte의 낭비를 하게 되는 셈이다. 이때 UTF-8을 사용하면 문자를 가변 크기로 처리할 수 있게 되고, ACSII코드로 표현이 가능하다면 이를 1byte만 사용하여 표현한다. 그러므로 UTF-8을 사용하면 6byte에 표현이 가능해진다.

파이썬 유니코드 인코딩

파이썬3는 유니코드로 모든 문자열을 표현한다고 했지만 사실 파이썬 내부적으로는 UTF-8 인코딩을 사용하지 않는다. 그 이유는 인덱스를 통해 개별 문자에 접근하기 어렵기 때문이다.

파이썬에서는 문자열 슬라이싱을 비롯하여 원하는 문자에 인덱스로 접근할 수 있는 다양한 방식을 제공하는데 만약 문자열을 UTF-8로 인코딩하게 되면 각 문자마다 바이트 길이가 달라져 전체 문자열을 스캔하지 않으면 원하는 인덱스의 위치를 찾을 수 없게 되어 빠르게 접근할 수 없게 된다. 따라서 고정 길이 인코딩 방식이 필요하며 파이썬은 문자열 단위로 다른 고정 길이 인코딩 방식을 적용해 이 문제를 해결한다.

만약 모든 문자열이 ASCII 범위 내에 있다면 Latin-1 인코딩(고정 1바이트 인코딩)을 사용하고 이외의 대부분의 문자열은 UCS-2(고정 2바이트 인코딩)로 2바이트 인코딩을 한다. 특수 기호, 그림 이모티콘, 희귀 언어 등이 포함된 문자열의 경우에는 UCS-4(고정 4바이트 인코딩)로 4바이트 인코딩을 한다. 이처럼 각 문자열에 포함된 문자 범위에 따라 서로 다른 고정 인코딩 방식을 택하여 내부적으로 파이썬은 문자열 슬라이싱을 포함한 원하는 인덱스에 빠르게 접근할 수 있다.