[프로그래머스] 가장 긴 팰린드롬 (Level 3, Python)

코딩테스트 연습 - 가장 긴 팰린드롬

아이디어

처음엔 삽질을 좀 했다.

string의 character를 하나씩 확인하면서 양쪽 투포인터를 써서 팰린드롬인지 확인해 나갈건데

1.  "abbba"  와 같은 경우

2번 인덱스의 b 기준으로 양쪽으로 퍼지면 된다.

그래서 l과 r을 i로 설정하여 양쪽으로 보내면 되는 것인데, 다음과 같은 경우를 보자.

l,r = i,i 로 설정하면 이런 반례가 생겨버린다.

2. "abccba"의 경우 l,r을 (i,i)로 셋팅하는게 아니라 (i,i+1)로 셋팅해줘야한다.

그런데 문자열 길이를 보고 짝수면 ? 뭐 등등 갖은 경우의 수를 생각하다가

 

결국 l,r 은 i,i 이거나 i,i+1이기 때문에 둘 다 돌려보고 높은값을 취하면 된다.

 

문제풀이

def solution(s):
	# 아무리 적어도 답은 자연수이므로 1이상입니다.
    maximum = 1
	# len(s) ==0이 없어도 되겠습니다.
    if len(s) == 1:
        return len(s)

	# string의 한글자씩을 기준으로 양옆으로 투포인터를 옮겨가며 확인합니다.
    for i in range(len(s)):
				# l,r 의 위치의 경우의 수가 두가지 있습니다. 
				# i,i에서 시작할지 i,i+1에서 시작할지.
        idx = [(i,i), (i, i+1)]
        for l,r in idx:
            cnt = 0
			# string의 범위를 넘지않게 설정하고
            while 0<=l and r <= len(s)-1:
				# 첫시작이 i,i라면 cnt를 +1시켜야합니다.
                if l==r:
                    cnt += 1
                    l ,r = l-1, r+1
                    continue
				# l,r의 포인터 위치가 다르고, 서로 가리키는 char가 같다면 팰린드롬이 성립
                elif s[l] == s[r]:
                    cnt += 2
                    l ,r = l-1, r+1    
				# 나머지는 팰린드롬이 꺠졌으니 while을 중단합니다.
                else:
                    break
			# 정답을 갱신해줍니다.
            maximum = max(maximum, cnt)
    return maximum