- 문제 이해
문자열 s가 주어질테니 가장 긴 팰린드롬을 substring해서 반환하는 문제입니다.
팰린드롬 : 거꾸로 뒤집어도 똑같은 문자열
예제만 보아도 알 수 있듯이 문제 이해 자체는 쉬운 문제입니다.
문제는 풀이인데,,
- 풀이 과정
음 우선 생각해야 할 것은 가장 '긴' 팰린드롬을 구해야 하는 것이니까
문자열 s 자체부터 길이가 1인 문자까지 길이를 -1 씩 빼면서 팰린드롬인지
확인하면 되지 않을까?
라는 생각을 하고 대충 시간 복잡도를 생각해봤는데, 이중 for문 안에 O(N) 짜리
팰린드롬인지 확인하는 함수를 넣는거니까 O(n^3)이라는 생각이 들었습니다.
O(n^3)..? Constraints 를 보면 1 <= s.length <= 1000 입니다.
1000의 3제곱이면 10억인데,,, 제가 알기로 파이썬이 1초에 2000만번 연산을 하니까
총 50초가 걸리는데 이야 절대 안되겠죠?
오케이 이건 O(n^2)으로 승부를 봐야겠습니다.
일단 팰린드롬인지 확인하는 함수는 무조건 O(N)이 걸리니까
for문 한번으로 어떻게든 견적을 내야 합니다.
문자열 s의 알파벳을 한번씩만 돌면서 팰린드롬인지 확인하는 방법...
이제 코드의 생김새는 대충 예상이 갑니다.
for i in range(len(s)):
# 팰린드롬인지 구하는 함수
# 모양은 isThisPalindrom(s[i])이런 느낌이겠죠??
그렇다면 팰린드롬에 대해 시각을 바꿔서 생각해 볼 필요가 있겠습니다.
뒤집어도 똑같은 문자열인데 문자열 하나로 시작해야만 한다.. 라고 생각하니까
아하 함수에 들어가는 문자 s[i]가 가운데 문자라고 생각하면??
투포인터의 포인트를 양쪽으로 잡아주고(left=i-1, right=i+1) 양쪽이 같은 경우에는
팰린드롬이니까 또 한칸씩 양쪽으로 밀어주고 하면서 검사하면? s[i]를 가운데로 하는
가장 긴 팰린드롬이 나오는 O(N)짜리 함수가 나오겠구나??
아무도 상처받지 않는 세계의 완성입니다.
바로 구현해보도록 하겠습니다.
- 정답 코드
class Solution(object):
def longestPalindrome(self, s):
def slide(left, right):
while left>=0 and right<len(s) and s[left] == s[right]:
# 왼쪽과 오른쪽이 같으면 팰린드롬
left-=1
right+=1
return s[left+1:right]
if len(s) == 1 or s == s[::-1]:
# 문자열 길이가 1 이거나 문자열 전체가 팰린드롬이면 바로 리턴 (최적화)
return s
ans = ""
for i in range(len(s)-1):
ans = max(ans, slide(i,i), slide(i,i+1), key = len)
# 길이가 짝수인 팰린드롬도 있을 수 있으니 i, i+1 도 추가
return ans