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

접근법

 

이중 loop을 돌면서 s[pivot] == s[target] 인 지점에서 팰린드롬인지 체크한다.

 

 

코드

첫 번째 코드

def solution(s):
    answer = 1
    
    if len(s) <=1:
        return answer
    
    for pivot in range(len(s)-1):
        for target in range(pivot+1,len(s)):
            if s[pivot] == s[target]:
                substring = s[pivot:target+1]
                if check(substring):
                    answer = max(answer, len(substring))
    return answer

def check(substring):
    target = len(substring)
    for i in range(target//2):
        if substring[i] != substring[target-i-1]: 
            return False
    return True
        

- 정확성 테스트는 다 통과했는데 효율성 테스트 하나가 시간초과 나는 바람에 틀렸다.

- O(n^3)이긴 한데.. 조금 더 최적화를 해야겠다.

- 생각해보니, 전체가 팰린드롬일 경우에는 내부가 팰린드롬인 것까지 확인해줄 필요가 없는데 이 코드에서는 그걸 하고있는 듯하다.

 

두 번째 코드

def solution(s):
    # s는 자연수이므로 무조건 1 이상
    answer = 1
    
    if len(s) <= 1:
        return answer
    
    
    for pivot in range(len(s) - 1):
        for target in range(len(s) - 1, pivot, -1):
        	# 같은 char을 찾고 
            if s[pivot] == s[target]:
                substring = s[pivot:target+1]
                # 이전에 찾았던 팰린드롬의 길이보다 substring의 길이가 더 크면
                # 팰린드롬인지 확인할 가치가 있으므로 check한다
                if answer < len(substring) and check(substring):
                    answer = max(answer, len(substring))
                    break
    return answer

# 팰린드롬인지 체크하는 함수
def check(substring):
    target = len(substring)
    for i in range(target//2):
        if substring[i] != substring[target-i-1]: 
            return False
    return True
        

로직

pivot은 왼쪽에서부터 탐색 for pivot in range(len(s) - 1)

target은 오른쪽 끝에서부터 pivot 전까지 탐색 for target in range(len(s) - 1, pviot, -1)

char이 같은 짝이 나오게되면 그 부분만 substring으로 따오고, 지금까지 찾은 팰린드롬 길이보다 크면 팰린드롬인지 체크 check(substring)

그 과정에서 나온 팰린드롬은 현재 target을 왼쪽으로 옮겨 찾는 팰린드롬보다 무조건 크기 때문에 탐색 종료(사진 참조)

pivot을 옮겨 다른 팰린드롬을 찾는다

 

위의 특징을 참고하여 최적화하였다