[파이썬]팰린드롬(Palindrome) 판별하기

Palindrome(회문)

 

거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등이다. 

ex) 기러기, madam, malayalam ....

 

 

Palindrome 판별 방법 

제일 처음과 제일 끝의 문자열 비교 ➞ 두번째와 끝에서 두번째 비교 ➞ 세번째와 끝에서 세번째 비교 .......

➞ 겹치는 지점까지 비교해서 두 문자가 같은지 다른지 판별하면 된다. 비교했을 때 같은 값이 나온다면 넘어가고 다른 값이 나오면 팰린드롬이 아니기 때문에 멈추면 된다. 

 

 

알고리즘 구현

 

Palindrome판별 방법을 재귀함수로 구현해보자. 

def palindrom(num_list, first, last):
    if(last <= first):
        return 1
    
    if(num_list[first] != num_list[last]):
        return 0
    else: 
        return (palindrom(num_list, first+1, last-1))

 

palindrome 문제를 재귀함수로 구현하게 되면 단점이있는데 바로 호출이 잦아지면 스택 오버플로우 문제를 격을 수도 있다. 재귀함수로 구현한 것과 loop으로 구현한것 모두 시간복잡도는 O(n)이지만 공간복잡도는 O(n), O(1)이기 때문에 loop가 공간적으로 더 효율이 크다. 

 

그래서 loop로도 구현해보자. 

def palindrome(word_list):
    n = len(word_list)
    for i in range(n // 2):  # 절반만 반복
        if word_list[i] != word_list[n - 1 - i]:  # 앞과 뒤에서 비교
            return 0
    return 1