이번엔 내가 항해99를 하면서 2주차 때 공부한 알고리즘에 대해서 기록해 보려고 한다. 책은 "파이썬 알고리즘 인터뷰"<저자 : 박상길>로 배웠다.
To. 혹시나 이 글을 보는 사람
문제풀이에 주석이 생각보다 많을텐데.. 이 글은 정말 내가 처음으로 개발자가 되려 입문할 때의 나처럼 아무것도 모를 것 같은 사람을 대상으로 생각하고 만들었다. 이해해주길 바란다....
1. 문자열 조작
문자열 조작이란, 문자열을 변경하거나 분리하는 등의 여러 과정을 말한다.
C언어처럼 문자형이 따로 없는 언어에서는 조작이 매우 까다로운 편이지만 대부분 언어에서는 별도의 문자열 자료형과 문자열을 조작하기 위한 다양한 기능들을 기본적으로 제공하고 있기 때문에, 굳이 제약을 두지 않는다면 활용하는 것이 좋다.
문자열 처리와 관련한 알고리즘이 쓰이는 대표적인 분야를 말하자면,
(1) 정보 처리 분야 : 어떤 키워드로 웹 페이지를 탐색할 때 문자열 처리 애플리케이션을 이용하게 된다. 특히 현대의 거의 모든 정보는 문자열로 구성되어 있으며 문자열 처리는 정보 처리에 핵심적인 역할을 한다.
(2) 통신 시스템 분야 : 문자 메세지나 이메일을 보낼 때 기본적으로 문자열을 어느 한 곳에서 다른 곳으로 보내게 된다. 이처럼 데이터 전송은 문자열 처리 알고리즘이 탄생한 기원이기도 하며, 데이터 전송에서 문자열 처리는 매우 중요한 역할을 한다.
(3) 프로그래밍 시스템 분야 : 프로그램은 그 자체가 문자열로 구성되어 있다. 컴파일러나 인터프리터 등은 문자열을 해석하고 처리하여 기계어로 변환하는 역할을 하며, 여기에는 매우 정교한 문자열 처리 알고리즘 등이 쓰인다.
문자열 조작에 대한 개념을 살펴봤으니 이제 문제를 몇개 살펴보자.
- 유효한 팰린드롬 (leetcode: 125. Valid Palindrome)
: 주어진 문자열이 팰린드롬인지 확인해라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.
- 입력
"A man, a plan, a canal: Panama"- 출력
true
- 입력
"race a car"- 출력
"false"
우선 팰린드롬이란, 앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장을 말한다.
위에 첫번째 예제의 입력된 문자열은 팰린드롬이라고 인식되어 true가 출력되었다. 그말은 < : , " ? / > 이와 같은 특수문자는 인식하지 않고 확인하는 것이 포인트다.
< 리스트를 이용한 풀이 >
def isPalindrome(self, s: str) -> bool: # 인자로 받는 s는 문자열(str)
# return은 bool형으로 반환
strs = [] # s로 들어온 문자열을 가공하여 담을 그릇
for char in s:
if char.isalnum(): # isalnum() : 들어온 char가 숫자, 문자인지 확인
strs.append(char.lower()) # if문이 맞으면 모든 문자를 소문자로 바꾸고 strs에 넣어준다.
# 양쪽을 하나씩 빼가면서 확인을 할 것이기 때문에 strs의 길이가 1보다 클때까지만 실행한다.
while len(strs) > 1:
if strs.pop(0) != strs.pop(): # pop()을 이용해서 빼면서 확인. ( 같지 않을시 False 반환)
return False
return True< 데크 자료형을 이용한 최적화 >
: 위에 있는 리스트를 활용해 pop()을 이용해 양쪽을 빼는 속도는 데크를 따라가지 못한다. 왜냐하면 데크(deque)는 양쪽으로 집어넣고 빼는 것에 최적화로 만들었기 떄문이다.
import collections
def isPalindrome(self, s: str) -> bool:
# 자료형 데크(deque) 선언 ( collections 모듈에 있어서 import 필수다.)
strs: Deque = collections.deque()
for char in s:
if char.isalnum:
strs.append(char.lower()) # 이부분은 위에 방법과 똑같다.
# 제일 중요한 부분이다. deque에서는 왼쪽끝(첫번째) 문자를 뽑을 때 popleft()를
# 쓴다. 이 때 리스트는 스텍(stack)을 기본으로 하고 있기 때문에 왼쪽 끝을 뽑을 때
# 시간 복잡도 O(n)이 걸린다. 하지만 deque는 O(1)이 걸리기 때문에 정말 빠르다.
while len(strs) > 1:
if strs.popleft() != strs.pop():
return False
return True< 슬라이싱을 이용한 풀이 >
: 정말 속도에 파격적이고 용도가 많이 쓰이는 슬라이싱을 통해서 풀이가 가능하다.
import re
def isPalindrome(self, s: str) -> bool:
s = s.lower() # 문자열을 소문자로 변경
# 정규 표현식으로 불필요한 문자를 필터링한다.
s = re.sub('[^a-z0-9]', '', s)
원본(s)과 뒤집은 s와 비교한다.
return s == s[::-1]2. 문자열 뒤집기 (leetcode: 344. Reverse String)
: 문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라.
- 입력
[ "h", "e", "l", "l", "o"]- 출력
["o", "l", "l", "e", "h"]
- 입력
["H", "a", "n", "n", "a", "h"]- 출력
["h", "a", "n", "n", "a", "H"]
이 문제가 까다롭게 느껴지는 것은 리턴 없이 리스트 내부를 직접 조작하라는 것에 있다. 그래서 문자열 내부를 스왑하는 형태로 풀이해야 한다.
< 투 포인터를 이용한 스왑 풀이 >
from typing import List
def reverseString(self, s: List(str)) -> None:
left, right = 0, len(s) - 1 # c언어와는 다르게 = 하나만 써서 동시선언하는 것은 정말 편하다.
# 왼쪽과 오른쪽 인덱스를 좁혀가면서 바꿔준다.
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right += 1< 파이썬다운 방식 풀이 >
def reverseString(self, s: List[str]) -> None:
s.reverse() # 이게 정말 끝이냐고 허무할 수 있지만 파이썬 내부함수엔
reverse()라는 함수가 있다. 이 함수는 문자열을 뒤집어 준다.3. 그룹 애너그램 (leetcode: 49. Group Anagrams)
: 문자열 배열을 받아 애너그램 단위로 그룹핑하라.
- 입력
["eat", "tea", "tan", "ate", "nat", "bat"]- 출력
[
["ate", "eat", "tea"],
["nat", "tan"],
["bat"]
]
애너그램이란, 일종의 언어유희로 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말한다. 애너그램의 우리말 예로는, '문전박대'를 '대박전문'으로 바꿔 부르는 단어 등을 들 수 있다.
< 정렬하여 딕셔너리에 추가 >
from typing import List # 자료형을 표시하는 것이지만 쓰려면 import 필요
import collections
def groupAnagrams(self, strs: List[str] -> List[List[str]]:
anagrams = collections.defaultdict(list)
# 키가 없어도 자동으로 디폴트 값으로 자동으로 만들어주는
# defaultdict 컨테이너는 정말 파격적인 함수이기 때문에 찾아보기 바란다.
for word in strs:
# 정렬하여 딕셔너리에 추가
anagrams['',join(sorted(word))].append(word)
return anagrams.values()
# get, setdefault를 사용할 수 있지만 정렬이 필요하기에 join을 사용하여 정렬해 키 값을 정해주었다.4. 가장 긴 팰린드롬 부분 문자열 (leetcode: 5. Longest Palindrome Substring)
: 가장 긴 팰린드롬 부분 문자열을 출력하라.
- 입력
"babad"- 출력
"bab" -> 이외에도 "aba"도 정답이다.
- 입력
"cbbd"- 출력
"bb"
=> 이 문제는 투 포인터가 중앙으로 확장하는 형태로 풀이해 보겠다.
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 - 1]:
left -= 1
right += 1
return s[left + 1, right - 1]
# 해당사항 없을 때 예외처리
if len(s) < 2 or s == s[::-1]:
return s
# 팰린드롬을 발견하면 넣을 변수 선언
result = ''
# 슬라이딩 윈도운 우측으로 이동
for i in range(len(s) - 1) # 물론 2칸씩 확인하는 포인터도 있으니 -1을 해준다.
# max함수를 사용해 최대 길이의 팰린드롬을 result에 넣어준다.
result = max(result,
expand(i, i+1),
expand(i, i+2),
key=len)
return result