프로그래머스 가장 긴 팰린드롬 (문자열 인덱싱, DP)

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

제한 사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

입출력 예

s	answer
"abcdcba"	7
"abacde"	3

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

풀이

• 머리가 안 돌아가고 무지성 코딩하고 싶어서 문제 길이가 짧은 걸 골라보았다.
  • 뭔가 초 간단한 문제 같아서 무지성으로 도전...
  • 일부 테케만 통과함... 반정도만 맞네? 왜 이래...ㅠ.ㅠ
    • 점점 괴로워짐... 무지성으로 코딩하고 싶엉...
• 삽질스...

def solution(s):
    answer = 0            

    i,j=0,0
    s_l = list(s)
    s_l = [ord(i) for i in s]
    s_r = s_l.copy()
    s_r.reverse()
    
    # print(s_l)
    # print(s_r)
    
    count = 0
    for i in range(len_s):
        for j in range(len_s-i):
            if s_l[i+j] == s_r[j]:
                count += 1
            else:
                if answer < count:
                    word_a = s_r[j-count:j]
                    word_b = word_a[::-1]
                    print(word_a, word_b)
                    if word_a == word_b:
                        answer = max(answer, count)
                count = 0
    if answer < count:
        word_a = s_r[j-count:j]
        word_b = word_a[::-1]
        print(word_a, word_b)
        if word_a == word_b:
            answer = max(answer, count)
    count = 0

    for i in range(len_s):
        for j in range(len_s-i):
            if s_l[j] == s_r[i+j]:
                count += 1
            else:
                if answer < count:
                    word_a = s_l[j-count:j]
                    word_b = word_a[::-1]
                    print(word_a, word_b)
                    if word_a == word_b:
                        answer = max(answer, count)
                count = 0
    if answer < count:
        word_a = s_l[j-count:j]
        word_b = word_a[::-1]
        print(word_a, word_b)
        if word_a == word_b:
            answer = max(answer, count)
    count = 0

    return answer

• 두번째 삽질스

def solution(s):
    answer = 1          
    count = 1
    set_s = list(set(s))
    word_indexes = {}
    
    if len(set_s) == 1:
        return len(s)
    
    while True:
        for c in s:
            begin = s.index(c)
            end   = s.rindex(c)
            if begin != end:
                word_indexes[c] = (begin, end)
        
        if len(word_indexes) == 0:
            break

        b2 = len(s)
        e2 = -1
        for k,v in list(word_indexes.items()):
            b,e = v[0],v[1]
            if b < b2:
                b2 = b
            if e2 < e:
                e2 = e
            if e-b+1 > count:
                count = e-b+1
                word1 = s[b:e+1]
                word2 = word1[::-1]
                if word1 == word2:
                    answer = max(answer, count)
        
        word_indexes.clear()
        s = s[b2:e2]

    return answer

• 여러번 뚝딱뚝딱 하다보니까 이젠 신물이 날 지경 ㅋㅋㅋ
  • 될 거 같은데 안되니까
    • 더 짜증남.
• 좀만 머리를 썼으면 쉽게 풀렸을 거 같은데...
  • 결국 포기하고
• for문을 무식하게 돌리면서 문자열 인덱싱으로 해결

def solution(s):
    answer = 1
    
    if len(set(s)) == 1:
        return len(s)
    
    for i in range(len(s)):
        for j in range(i,len(s)):
            word1 = s[i:j+1]
            word2 = word1[::-1]
            if word1 == word2:
                answer = max(answer, len(word1))

    return answer

정확성  테스트
테스트 1 〉	통과 (0.05ms, 10.2MB)
테스트 2 〉	통과 (0.03ms, 10.1MB)
테스트 3 〉	통과 (2.43ms, 10.2MB)
테스트 4 〉	통과 (2.80ms, 10.3MB)
테스트 5 〉	통과 (1.37ms, 10.3MB)
테스트 6 〉	실패 (1.38ms, 10.3MB)
테스트 7 〉	통과 (2.66ms, 10.1MB)
테스트 8 〉	통과 (2.76ms, 10.3MB)
테스트 9 〉	실패 (1.46ms, 10.1MB)
테스트 10 〉	실패 (1.27ms, 10.3MB)
테스트 11 〉	통과 (1.34ms, 10.1MB)
테스트 12 〉	통과 (1.80ms, 10.1MB)
테스트 13 〉	통과 (1.27ms, 10.2MB)
테스트 14 〉	실패 (5.24ms, 10.2MB)
테스트 15 〉	통과 (4.65ms, 10.2MB)
테스트 16 〉	통과 (8.61ms, 10.1MB)
테스트 17 〉	통과 (0.01ms, 10.2MB)
테스트 18 〉	통과 (0.01ms, 10.2MB)
테스트 19 〉	실패 (1.27ms, 10.2MB)
테스트 20 〉	통과 (1.47ms, 10.1MB)
테스트 21 〉	실패 (1.45ms, 10.1MB)
효율성  테스트
테스트 1 〉	실패 (2088.40ms, 10.3MB)
테스트 2 〉	통과 (2255.26ms, 10.2MB)

• 고수의 풀이
  • 대부분 2중 for문 + 문자열 인덱싱으로 풀었고...
  • DP 풀이. 고급져 보인다. ㅠ.ㅠ

def solution(s):
    dp = [[0]*len(s) for _ in range(len(s))]

    answer = 1
    for i in range(len(dp)):
        dp[i][i] = 1
        answer = 1
    for i in range(len(dp)-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = 1
            answer = 2

    for k in range(3, len(dp)+1):
        for i in range(len(dp)-k +1):
            j = i + k -1
            if dp[i+1][j-1] == 1 and s[i] == s[j]: 
                dp[i][j] = 1
                answer = k
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.03ms, 10.3MB)
테스트 3 〉	통과 (0.61ms, 10.3MB)
테스트 4 〉	통과 (0.58ms, 10.2MB)
테스트 5 〉	통과 (0.61ms, 10.3MB)
테스트 6 〉	통과 (0.58ms, 10.3MB)
테스트 7 〉	통과 (0.62ms, 10.3MB)
테스트 8 〉	통과 (0.61ms, 10.4MB)
테스트 9 〉	통과 (0.75ms, 10.2MB)
테스트 10 〉	통과 (0.61ms, 10.4MB)
테스트 11 〉	통과 (0.73ms, 10.3MB)
테스트 12 〉	통과 (0.97ms, 10.2MB)
테스트 13 〉	통과 (0.57ms, 10.3MB)
테스트 14 〉	통과 (2.16ms, 10.4MB)
테스트 15 〉	통과 (1.96ms, 10.4MB)
테스트 16 〉	통과 (2.09ms, 10.5MB)
테스트 17 〉	통과 (0.01ms, 10.4MB)
테스트 18 〉	통과 (0.01ms, 10.2MB)
테스트 19 〉	통과 (0.55ms, 10.2MB)
테스트 20 〉	통과 (0.67ms, 10.3MB)
테스트 21 〉	통과 (0.69ms, 10.2MB)
효율성  테스트
테스트 1 〉	통과 (538.53ms, 58MB)
테스트 2 〉	통과 (612.13ms, 58MB)