프로그래머스 12904 가장 긴 팰린드롬 파이썬 풀이

난이도 : Lv. 3

풀이일 : 2411074

https://school.programmers.co.kr/learn/courses/30/lessons/12904

프로그래머스

---

문제

---

아이디어

• 투 포인터를 사용해 팰린드롬인지 여부를 검사하자
• 왼쪽 인덱스를 하나씩 늘려가고, 각 왼쪽 인덱스마다 오른쪽 인덱스는 제일 뒤에서부터 줄어들게 설정하자

---

풀이 코드

def solution(s):
    answer = 0
    
    for i in range(len(s)):
        for j in range(len(s) - 1, i - 1, -1):
            # 최댓값 유망성 검사
            if j - i + 1 < answer:
                continue
            palindrome = True
            left, right = i, j # 포인터
            while left < right:
            	# 포인터가 가리키는 글자가 같으면, 다음 글자 검사
                if s[left] == s[right]:
                    left += 1
                    right -= 1
                # 포인터가 가리키는 글자가 다르면 종료
                else:
                    palindrome = False
                    break
            # 팰린드롬이라면, 길이 비교 후 최댓값 저장
            answer = max(answer, j - i + 1) if palindrome else answer
    return answer

• i는 가장 왼쪽부터 오른쪽으로 증가하며, j는 제일 오른쪽 끝부터 i까지 감소한다.
• 만약, 현재 검사하는 회문의 길이가 최댓값이 될 가능성이 없다면, 더이상 진행하지 않고 다음 반복을 수행한다.
• palindrome으로 팰린드롬인지 아닌지를 저장한다.
• left 포인터가 right보다 작은 동안, 두 포인터가 가리키는 글자를 비교한다.
• 두 포인터가 가리키는 글자가 같다면, 동시에 한 칸씩 늘리고 줄여 가운데로 모이게 한다.
• 어느순간 두 포인터가 가리키는 글자가 다르다면, 팰린드롬이 아니므로 종료한다.
• 팰린드롬이라면, answer에 저장된 것과 현재 찾은 팰린드롬 중 큰 값을 answer에 할당한다.

---

느낀점

• 지금 검사하는 구간이 최댓값이 될 가능성이 있는지 확인하는 부분을 추가하기 전에는 시간초과가 발생하였다.
• 팰린드롬 문제가 익숙하지 않아서 시간이 조금 걸렸는데, 낯선 문제들을 좀 찾아서 푸는 연습을 해야겠다. 그리고 자바로 풀어봐야지!

---

다른 코드

def solution(s):
    answer = 1

    for i in range(len(s)):
        for j in range(len(s), i, -1):
            if s[i:j] == s[i:j][::-1]:
                answer = max(j - i, answer)
                break
            
    return answer

• 문자열을 뒤집어서 비교하는 방식으로 풀려고 시도해보았다.
• i는 왼쪽부터 증가하고, j는 오른쪽부터 i까지 감소한다.
• i부터 j까지의 문자열을 뒤집어 비교하는 방식이므로, 팰린드롬 길이를 기록했다면, 다음 i에 대한 검사를 수행한다.