문자열 조작: 애너그램 / 필린드롬 부문 문자
input = "abccbaz"
# 필랜드롬인지 판정하는 함수
def is_palindrome(sub_str:str) -> str:
return sub_str == sub_str[::-1]
# 가장 긴 필랜드롬
def search_longest_palindrome(string:str) -> str:
# 문자열의 길이가 2이하인데, 0번, 1번 문자열이 같은 경우
if len(string) <= 2:
if is_palindrome(string):
return string
longest_palindrome = str()
for start_idx in range(1, len(string)):
for window in range(1, start_idx):
substring = string[start_idx-window:start_idx+window]
if is_palindrome(substring):
if len(longest_palindrome) < len(substring):
longest_palindrome = substring
return longest_palindrome
search_longest_palindrome(input)
애너그램(Anagram)이란?
애너그램은 문자를 재배열하여, 다른 뜻을 가지는 단어로 바꾸는 것을 말한다. 예를 들어, 리그 오브 레전드의 챔피언과 "마오카이(Maokai)"은 "I am oak(떡갈나무)"와 같이 단어의 수와 각각의 문자열이 동일한데, 순서만 재배치함으로써, 다른 뜻을 가지는 단어들을 의미한다. 파이썬에서 단어들을 이런 애너그램 단위로 묶으려면 어떻게 해야할까? 다음과 같은 문제가 주어졌다고 가정하자.
아래와 같이 문자열이 주어졌을 때, 애너그램단위로 문자열 6개를 각각 유니크한 애너그램 단위로 묶고자한다.
inputs = ["education", "auctioned", "cautioned", "eat", "ate", "bet"]
솔루션
defaultdict을 이용하면, 바로 Key의 생성없이 Key, value의 할당이 가능하다. 각각의 인자를 list에 바로 저장할 때, 문자열이 애나그램인지 파악하기 위해서, 애너그램여부를 sorted()을 이용해서 정렬해서 파악한다. sorted()은 리스트, 문자열을 인자로 받을 수 있어서, 이를 이용해서 "".join(sorted(word))의 구문을 실행시키면, 정렬된 문자열이 반환된다.
# python3.x
inputs = ["education", "auctioned", "cautioned", "eat", "ate", "bet"]
# Solution
from collections import defaultdict
def sorted_words(inputs):
anagram_groups = defaultdict(list)
for idx, word in enumerate(inputs):
anagram_groups["".join(sorted(word))].append(idx)
return anagram_groups
팰린드롬(Palindrome, 회문)
팰린드롬(Palindrome)은 흔히 "요기요"는 거꾸로 해도 "요기요", "소주 만 병 만 주소"와 같이, 거꾸로 해도 똑같은 의미의 문장이 되는 문자열을 의미한다. 팰린드롬은 주어진 문자열이 있을 때, 문자열내에 팰린드롬이 있을 수도 있고, 없을 수도 있다. 예를 들어, "소주 주세요"와 같은 문자열은 팰린드롬이 없지만, "이 글의 원어는 국립국어원의 출처입니다"과 같이 팰린드롬이 모든 문자열이 아닌, 전체 문자열의 부분으로 가지고 있는 경우도 있다. 이렇듯, 문자열이 주어졌을 때, 가장 긴 팰린드롬을 찾아보자.
input = "abccbaz"
솔루션: 1) 우선 필랜드롬인지 검사하는 함수가 하나 독립적으로 있으면, 디자인이 쉬워진다. 그 후, 포인터 2개(첫 번째는 시작포인터, 두 번째는 윈도우)를 이용해서 검사를 진행한다.
아래와 같이 문자열이 주어졌을 때, 필랜드롬은 적어도 문자열의 길이가 2인 경우만 취급한다. 따라서, 필랜드롬의 문자가 2개이하면서, 0번, 1번의 문자가 동일한 경우는 조기 return을 시켜줄 수 있다.
# 가장 긴 필랜드롬
def search_longest_palindrome(string:str) -> str:
# 문자열의 길이가 2이하인데, 0번, 1번 문자열이 같은 경우
if len(string) <= 2:
if is_palindrome(string):
return string
그 외의 대부분의 경우를 위한 함수를 작성할 때는 아래와 같이 로직을 짤 수 있다. 1) 필랜드롬을 검사하기위한 시작인덱스(start_idx)는 0이 아니라 1부터 시작한다. 2) 윈도우사이즈는 start_idx을 넘으면 indexError가 날 것이기에, start_idx을 넘으면안된다. 또한 start_idx은 1부터 시작한다(0이면 시작점의 알파벳 하나를 비교하는 꼴이기 때문). 그리고, 가장 긴 필랜드롬을 찾는 것이기 때문에, 중간에 저장해놓을 변수를 하나 지정해서 다음과 같이 작성해볼 수 있다.
