[프로그래머스 2단계] 알고리즘 27. 가장 긴 팰린도롬

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 27. 가장 긴 팰린도롬

앞뒤를 뒤집어도 똑같은 문자열을 palindrome이라고 합니다. longest_palindrom함수는 문자열 s를 매개변수로 입력받습니다. s의 부분문자열중 가장 긴 palindrom의 길이를 리턴하는 함수를 완성하세요. 예를 들어 s가 토마토맛토마토이면 7을 리턴하고 토마토맛있어이면 3을 리턴합니다.

def longest_palindrom(s):

# 함수를 완성하세요

return 0

# 아래는 테스트로 출력해 보기 위한 코드입니다.

print(longest_palindrom("토마토맛토마토"))

print(longest_palindrom("토마토맛있어"))

풀이:

이전에 팰린도롬 문제를 문자열을 그대로 뒤집어서 비교하는 코드로 푼 것을 기억하자 파이썬으로 다음과 같이 표현할 수 있다.

s == s[::-1]

다른 언어와 달리 굉장히 간편하게 표현된다. 문자열을 다루는데는 파이썬만한 언어는 없다고 생각하는 바이다. 이제 문자열 중 부분 문자열 중 가장 긴 팰린도롬을 찾으면 된다. 나는 순차적으로 이 문제를 풀었다. 알고리즘은 다음과 같다.

1. 문자열 첫 문자부터 끝 문자까지 팰린도롬을 찾는다.
2. 각 문자에 대해서 문자열 끝 위치부터 문자의  위치까지 차례로 부분 문자열이 팰린도롬인지 판단한다
3. 찾은 팰린도롬에 대해서 최대 길이를 계속 갱신해준다.
   

대충 설명만 들어서는 명확하지 않는데 예제를 보면 이해가 더 쉽게 될 것이다. 예를 들어 "토마토맛있어"라는 문자열이라면 다음과 같이 탐색한다.

첫 위치 토

토마토맛있어 -> 팰린토롬(X)

토마토맛있    -> 팰린토롬(X)

토마토맛       -> 팰린토롬(X)

토마토          -> 팰린토롬(O)  -> 3저장

두번째 마

마토맛있어     ->팰린토롬(X)

마토맛있        ->팰린토롬(X)

마토맛           ->팰린토롬(X)

마토              ->팰린토롬(X)

마                 ->팰린토롬(O) -> 1 저장

세번째 토

....

이제 필자의 의도를 정확히 알아차릴거라 생각한다. 핵심은 이중 반복이다. 코드를 보며 이해해보자. 나의 코드는 다음과 같다.

def longest_palindrom(s):

max = 0 #문자열 최대 길이를 저장할 변수

for i in range(0, len(s)): #첫 위치부터 끝 위치까지 문자열을 순회

for j in range(len(s), i, -1): #문자열 끝에서부터 탐색 문자 위치까지 거꾸로 부분 문자열 탐색

if s[i:j] == s[i:j][::-1]: #부분문자열 i ~ j가 팰린도롬이라면

max = (j - i) if (j - i > max) else max #그 길이가 최대라면 갱신한다. j-i = len(s)

break #부분 문자열은 끝에서부터 검사하기 때문에 찾는 즉시 그 길이가 최대이다.

return max

주석과 하께 읽으면 더 이해가 잘 갈 것이다. 이렇게만 하면 심심하기 때문에 재귀문으로 바꿔보겠다. 잘 짜여진 반복문은 재귀문으로 쉽게 바꿀 수 있다. 여기서 반복적으로 하는 일이 다음과 같이 두가지가 있다.

1. 먼저 문자열이 팰린도롬인지 판단한다.
2. 맞다면 최대 길이를 갱신한다. 아니라면 문자열 길이를 줄인다.
   

이제 한 번 바꿔보겠다. 코드는 다음과 같다.

def longest_palindrom_rec(s):

return len(s) if s == s[::-1] else max(longest_palindrom(s[:-1]), longest_palindrom(s[1:]))

여기서 길이를 갱신하는 코드는 else max(...) 부분이다. 첫 번째 인자는 문자열을  끝부터 줄인 부분 문자열들의 결과를 찾고 두 번째 인자는 시작 위치부터 줄인 부분 문자열들의 결과를 탐색한다. 이제 2단계 문제도 다 풀었다. 2단계의 11문제를 다 푼 자신에게 박수! 다음부터 3단계에 돌입한다.