[프로그래머스] 가장 긴 팰린드롬 찾기

Saturday. May 05, 2018 - 6 mins

Summary:

문자열 s를 매개변수로 받아 문자열의 부분문자열 중 팰린드롬이 되는 가장 긴 문자열의 길이를 반환하는 메소드를 만드는 문제

굉장한 삽질을 했기 때문에 한 번에 정답을 알고 싶으신 분은 마지막 풀이를 보시길.

Palindrome(회문)이란? : 역순으로 뒤집어도 같은 형태를 띠는 문장.

문제설명

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

“토마토” reverse “토마토” (길이 3)
“토마토맛토마토” reverse “토마토맛토마토” (길이7)

첫 풀이

첫 풀이는 정답도 아닐뿐더러 매우 이해하기 힘든 코드이다. 팰린드롬의 규칙을 잘못 이해하고 짠 코드이기 때문이다. 잘 못된 풀이지만 나와 같은 착각(?)을 한 사람들도 있을 수 있기에 설명을 해보겠다.

오답주의!!!

팰린드롬의 길이들을 저장할 p_list 를 만듦
부분문자열의 기준점 (팰린드롬이 될 문자열의 정중앙)을 순서대로 이동시킴
기준점의 왼쪽과 오른쪽을 뒤집은 부분이 같으면 팰린드롬 이다.
팰린드롬을 p_list에 넣는다.
p_list에서 가장 큰 값을 리턴 한다.

def longest_palindrom(s):
    p_list = []
    for i in range(len(s)):
        for j in range(i):
            if(s[j:i] == s[i+1:i+1+len(s[j:i])][::-1]):
                p_list.append(len(s[j:i+1+len(s[j:i])]))

    return max(p_list)

1. 팰린드롬의 길이들을 저장할 p_list 를 만듦

p_list = []

문자열에서 부분문자열 중 palindrom의 길이가 저장될 배열

2. 문자열의 기준점 을 순서대로 이동시킨 후 기준점의 왼쪽과 오른쪽을 뒤집은 부분이 같은 팰린드롬 의 길이를 p_list에 넣는다.

for i in range(len(s)):
    for j in range(i):
        if(s[j:i] == s[i+1:i+1+len(s[j:i])][::-1]):
            p_list.append(len(s[j:i+1+len(s[j:i])]))

이중 for문을 만들어 문자열의 길이만큼 순서대로 증가하는 i 값(부분 문자열의 중앙 index)과 i 값까지 증가하는 j 값(기준점을 기준으로 앞부분과 뒷부분을 가리킬 index)을 설정한다.

문자열의 기준점의 앞부분 s[j:i] 와 기준점(i) 이후 앞부분과 같은 길이만큼 뒤집은 부분문자열 s[i+1:i+1+Len(s[j:i])][::-1] 이 서로 같으면 팰린드롬이다.

잘못된 풀이

ex)
s="토마토맛토마토"
i=3
j=0

# s[3]은 "맛"이고 "맛"을 기준으로 앞과 뒤의 문자열의 길이를 증가시키며 같은지 비교한다.
s[0:3] == "토마토"
s[3+1:3+1+3 ][::-1] == "토마토" # s[4:7]

len(s[j:i+1+len(s[j:i])]) # 7

여기서 잘 못된 방법을 사용하였다. 일단 팰린드롬의 길이는 무조건 홀수가 아니다. 나는 팰린드롬을 비교할 때 무조건 홀수라고 생각하고 길이가 홀수인 부분문자열의 중앙 index를 기준점으로 앞부분과 뒷부분이 같으면 팰린드롬이 되게 하였다. 문자열이 “토마토토마토”처럼 길이가 짝수이면서 가장 긴 길이인 “토마토토마토” 를 확인하지 않고 “토마토토마토”만 확인하여 팰린드롬으로 인식한다.

그 때문에 길이가 짝수인 팰린드롬은 검사하지 못한다.

3. p_list에서 가장 큰 값을 리턴 한다.

return max(p_list)

p_list에 있는 값들 중 가장 큰 값을 리턴해준다.

두 번째 풀이

첫 풀이가 뭐가 잘못되었는지 몰라서 몇 시간을 고생하고 문제풀이 방식을 아예 변경하였다.

문자열 s => “우리집방울토마토는토마토같다나는초왕방울울방왕초등학교를다닌다”
팰린드롬은 볼드 처리된 부분 => “우리집방울토마토는토마토같다나는초왕방울울방왕초등학교를다닌다”

이런 문자열을 검사하기 위해서는 첫 풀이처럼 기준점을 반으로 나눠 비교하면 안 된다.

그럴 때 짝수 팰린드롬인 “초왕방울울방왕초”의 앞의 “토마토 맛 토마토”밖에 찾지 못한다. 또한, 비교방식을 짝수길이도 비교할 수 있게 바꾼다 해도 모든 경우를 검사하지 않으면, 뒤에 더 긴 팰린드롬을 지나칠 수 있다.

그 때문에 비교할 문자열의 크기를 지정하고 지정한 길이만큼의 부분문자열이 문자열에 포함된 모든 경우 를 검사해야 한다.

문자열 길이를 줄이면서 비교한다.
단, 한쪽으로만 줄이는 게 아니라 앞뒤로 줄여야 함
줄인 문자열을 뒤집어서 같은 문자열(팰린드롬)이 있는지 비교해야 함
팰린드롬 중 가장 길이가 긴 팰린드롬의 길이를 반환

def longest_palindrom(s):
    # 비교할 문자열의 길이를 지정 : 문자열의 제일 긴 길이부터 0까지 -1씩 줄여나감
    for i in range(len(s), 0, -1):
        # 짧아진 길이 만큼 앞뒤로 이동시키며 비교 : 줄인 길이 만큼 문자열의 시작점을 이동시키며 비교해야 한다. 때문에 +1을 해준다.
        for j in range(len(s) - i + 1):
            # j는 부분 문자열의 시작 index, i는 부분 문자열의 길이
            if(s[j:j+i] == s[j:j+i][::-1]):
                return i

1. 문자열 길이를 매개변수로 받은 문자열의 길이부터 1씩 줄이고 가능한 부분문자열을 검사한다.

for i in range(len(s), 0, -1):
    for j in range(len(s) - i + 1):

i는 s의 부분문자열의 길이를 지정해 줄값이다. 부분 문자열의 최대길이는 매개변수로 받은 s의 길이부터 0까지 -1씩 줄여나가야 한다. 그리고 i 길이만큼 존재하는 s의 모든 부분문자열을 검사해야 한다.

이때 부분문자열은 최대 길이에서 부분문자열의 길이를 뺀 값에 +1한 만큼 존재할 것이다.

예를들어

s = "토마토맛토마토"
i=3 # i값이 3이면
length = len(s)-i+1 # 부분 문자열은 5개

for j in range(length): # j는 0,1,2,3,4 까지 순서대로 증가
# 토마토, 마토맛, 토맛토, 맛토마, 토마토

2. 부분 문자열이 팰린드롬인지 확인하고 부분문자열의 길이를 리턴한다.

if(s[j:j+i] == s[j:j+i][::-1]):
    return i

i값은 부분문자열의 길이를 값이다. j값은 부분문자열이 시작할 index이다. i 값은 1씩 줄어들기 때문에 if 문의 조건에 맞을 때 가장 긴 i 값(부분문자열의 길이)이 반환된다.