programming
알고리즘 - palindrome 회문 파이썬으로 구현하기
by Kitle · 2020. 07. 21.
오늘은 palindrome, 즉 회문에 대해 파이썬으로 구현해보겠습니다.
회문 : 회문 또는 팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.
보통 한글로 '토마토' 등의 단어를 회문이라고 합니다. 거꾸로 읽어도 동일한 단어죠.
파이썬에서는 어떻게 구현할까요?
우선 알고리즘으로 파악해 봅시다.
'첫번째 회문의 특징은 거꾸로 읽어도 제대로 읽은 것과 같다' 는 점이 포인트입니다.
원 문장 A를 기준으로 뒤집은 문장 B 를 구합니다.
그리고 A와 B가 같다면 회문, 아니면 회문이 아닌것이겠죠?
파이썬으로 바로 구현해 보겠습니다.
def solution_reverse(s):
if s == s[::-1]:
return True
else:
return False
s='aba' 등의 회문 문자열이 주어졌을 때 함수로 다음과 같이 구현할 수 있겠습니다.
첫번째 s 는 원문입니다. s[::-1] 은 원문을 반대로 뒤집은 문자열입니다. 슬라이싱 기능을 활용하여 문자열을 쉽게 뒤집을 수 있습니다.
따라서 원문과 뒤집은 문자열을 == 연산자로 비교하여 연산을 할 수 있겠습니다. == 결과는 True False로 리턴되므로 참 거짓만 판별하길 원하면 더 간단하게 쓸 수 있습니다.
def solution_reverse(s):
return s == s[::-1]
결과가 참이면 True, 틀리면 False 가 Return 될겁니다.
여기까지만 하면 좀 아쉽죠.
두번째로는 가운데를 기점으로 맨 왼쪽과 맨 오른쪽의 문자를 비교하고, 두번째 문자와 맨 끝에서 두번째 문자를 비교하고... 이렇게 중간까지 비교해서 모두 같으면 회문이라고 볼 수도 있습니다.
문자열 수가 짝수라면 / 2 한만큼을 비교하면 되고 홀수라면 가운데 수는 비교할 필요는 없습니다.
파이썬으로 바로~ 구현해보죠.
def solution_index(s):
for idx, item in enumerate(s[:len(s) // 2]):
if item != s[-1-idx]:
return False
return True
각 위치 index 가 필요하므로 여기서 enumerate 를 활용했습니다.
비교는 절반으로 나누어 비교하면 되므로 시작~중간까지만 반복합니다. s[:len(s) // 2] 를 통해 시작부터 중간 index까지만 계산합니다.
예를들어 총 길이가 10 이라면 index는 0~9 총 10개 입니다. 길이를 반으로 나누면 5 가 되므로 s[:5] 라서 실제로는 0,1,2,3,4 만 비교하게 됩니다. s[:5]는 5보다 작은 값까지를 슬라이스 합니다.
0,1,2,3,4 는 각각 9,8,7,6,5 와 비교해야 합니다.
0,1,2,3,4 는 item 으로 순회되고, s[-1-idx]: 로 인해 s[-1-0] 즉 s[-1] s의 맨 뒤의 첫번째 원소 즉 9번 인덱스 마지막 값이 됩니다. s[-1] , s[-2] 이렇게 맨뒤의 원소 순으로 접근할 수 있습니다. 시작 인덱스를 뒤에서 -로 처리해주어 저렇게 됩니다.
그리고 두 개의 값을 비교했을 때 하나라도 다르면 회문이 아니므로 바로 결과를 False 로 리턴해줍니다. 마지막까지 모두 같다면 True를 리턴하겠죠?
상당히 긴 문자열의 경우이고 첫번째 알고리즘에서 문자열을 뒤집는데 시간이 더 걸리게 된다는 가정하에 문자열 값이 초반에 틀린 경우는 두번째 알고리즘이 아마 약간은 False 리턴이 빨라 질듯 합니다. 다만 거의 마지막에 문자열이 틀린 경우라든지 True인 경우는 비슷하겠지요. 그러나 현실적으로 문장의 길이가 그다지 긴 경우도 없을 것이라 생각되어.. 개인적으로는 일반적인 경우는 첫번째 알고리즘으로 해도 크게 시간이 오래 걸리는 알고리즘이 아니어서 첫번째 알고리즘이 일반적으로 써도 무난할 것 같네요.
이상 마칩니다.
