[프로그래머스💯] 코딩테스트 연습 > 연습문제 > 가장 긴 팰린드롬

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

def solution(string):
    end = len(string)-1

    def find(i, i2 = -1):
        res = 2  # 가운데가 2개로 볼때
        if i2 == -1:  # 가운데 1개 기준으로볼때
            i2 = i
            res = 1
        j = 1  # 커지는 수
        while i2 + j <= end and i - j >= 0:
            if string[i2+j] == string[i-j]:
                res += 2
            else:
                return res
            j += 1
        return res
    answer = 1
    for i in range(1, len(string)-1):
        if string[i] == string[i+1]: # 2개짜리 검사
            answer = max(answer, find(i), find(i, i+1))
        else:
            answer = max(answer, find(i)) # 1개짜리 검사
    print(answer)
    return answer


solution('123123')

 

풀이)

팰린드롬을 검사하는데에 내가 쓴 방법은 이러하다.

 

1. 가운데 기준이 될 숫자를 고른다. * 가운데 숫자는 1개 혹은 2개가 될 수 있다!!!! (예 : 12321, 123321 ) 

-> 그러므로 1개를 고를 경우, 2개를 골랐을 경우를 모두 생각해줘야한다.

2. 그 숫자를 시작으로 앞뒤가 같은지 확인하며 같다면 2씩 더해준다.

3. 2를 같지 않을때 까지 반복한다.

4. 1~3 과정을 통해 특정 위치에서의 가장 긴 팰린드롬을 쉽게 구할 수 있다.

for 문으로 문자열의 2번째 인덱스부터 끝까지 각각을 기준으로 잡아서 1~3 과정을 거친다. 

 

솔직히 풀고 나서도 , 더 좋은 방법이 있을 것 같다거나, 최적화 할 수 있을 것 같은 찜찜함이 든다.....

혹시 더 좋은 방법 있으면 알려주세요!!! 😊

 

 

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges