[알고리즘] Programmers 가장 긴 팰린드롬 #Python

[Programmers] 가장 긴 팰린드롬 바로가기

📍 문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

---

📍 제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

📍 입출력 예

s	answer
"abcdcba"	7
"abacde"	3

---

📍 입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

---

📍 풀이

💡 고찰

• 경우에 따른 조건과 전수 조사 방식을 통해 문제를 해결하였다.
• 팰린드롬의 길이에 따라 즉, 길이가 짝수 혹은 홀수인지에 따라 고려해야할 사항을 적용하였다.
• 길이가 짝수인 팰린드롬은 문자열을 반으로 나누었을 때 앞, 뒤의 문자열이 대칭을 이루어야 한다.
  • abba → ab, ba 대칭
• 길이가 홀수인 팰린드롬은 가운데 문자열을 기준으로 앞, 두의 문자열이 대칭을 이루어야 한다.
  • abcba → c 를 기준으로 ab, ba 대칭
• 문자열의 길이가 짝수인 경우와 홀수인 경우에 고려해야할 점이 약간 다르다.
• 따라서 문자열의 길이가 짝수인 경우와 홀수인 경우에 대한 조건을 세워서 알고리즘을 작성하였다.

📌 문제 풀이

✏️ [1] answer값 초기화

if N > 1 and s[0] == s[1]: answer = 2
else: answer = 1

• 문제의 제한사항을 참고하면 문자열의 길이는 2,500 이하의 자연수 임을 알 수 있다.
• 문자열(s)의 길이가 2 이상이고 첫번째 문자와 두번째 문자가 같다면 answer 의 값을 2로 초기화한다.
  • aabcde 문자열 중 첫번째, 두번째 문자를 원소로 하는 부분 문자열인 aa 문자열을 앞뒤를 뒤집어도 aa 가 되므로 팰린드롬이다.
• 문자열(s)의 길이가 1이거나 첫번째, 두번째 문자가 다르다면 answer 의 값을 1로 초기화한다.
  • 예를들어 문자열의 길이가 1인 a 문자열은 앞뒤를 뒤집어도 a 가 되므로 팰린드롬이다.

✏️ [2] 팰린드롬 길이 계산

def lengthPalindrome(start,end):
    length = end - start - 1
    while start >= 0 and end < N and s[start] == s[end]:
        length += 2
        start, end = start-1, end+1
    return length

• lengthPalindrome 함수의 인자인 start, end 는 문자열의 시작과 끝 지점이다.
• 팰린드롬 문자열의 길이(length)의 초기값은 문자열의 시작과 끝 지점의 차이값이다.
• 문자열의 시작과 끝 지점이 주어진 문자열(s)를 벗어나지 않고, 문자열의 시작과 끝 지점의 값이 같다면
  • 팰린드롬 문자열의 길이(length) 값을 2 증가시키고
  • 문자열의 시작과 끝 지점의 값을 1 증감시킨다.

✏️ [3] 짝수, 홀수 길이 팰린드롬

for i in range(1,N-1):
    # 홀수 팰린드롬
    if s[i-1] == s[i+1]:
        answer = max(answer, lengthPalindrome(i-1,i+1))
    # 짝수 팰린드롬
    if s[i] == s[i+1]:
        answer = max(answer, lengthPalindrome(i,i+1))

• 문자열의 길이가 홀수인 팰린드롬
  • 현재 위치(i)를 기준으로 양 옆의 문자가 같다면 양 옆의 위치(i-1, i+1)를 인자로 하는 lengthPalindrome() 함수의 결과값을 구한 후 최대 값을 갱신한다.
• 문자열의 길이가 짝수인 팰린드롬
  • 현재 위치(i)의 문자와 오른쪽의 문자(i+1)가 같다면 해당 위치(i, i+1)를 인자로 하는 lengthPalindrome() 함수의 결과값을 구한 후 최대 값을 갱신한다.

✍ 코드

def solution(s):
    
    s, N = list(s), len(s)
    # answer 초기화
    if N > 1 and s[0] == s[1]: answer = 2
    else: answer = 1
    
    # 팰린드롬 길이 계산
    def lengthPalindrome(start,end):
        length = end - start - 1
        while start >= 0 and end < N and s[start] == s[end]:
            length += 2
            start, end = start-1, end+1
        return length

    for i in range(1,N-1):
        # 홀수 팰린드롬
        if s[i-1] == s[i+1]:
            answer = max(answer, lengthPalindrome(i-1,i+1))
        # 짝수 팰린드롬
        if s[i] == s[i+1]:
            answer = max(answer, lengthPalindrome(i,i+1))
    
    return answer