(MEDIUM) LeetCode No.5 - Longest Palindromic Substring 풀러가기

문제

• 입력된 문자열에서 가장 긴 팰린드롬을 반환할 것
• 가장 긴 팰린드롬의 경우가 여러 개 나오면 무엇을 반환해도 상관없음.
  ex) 'aba', 'bab' 라면 둘 중 아무거나 반환해도 됨.

문제 풀이

문제 푸는데는 실패했다. 2시간 50분 쯤에서 풀이를 멈췄다. 답안은 2개를 만들었는데 모두 메모리 초과가 되어 실패했다.
책을 보니 슬라이싱 윈도우라는 개념을 도입해서 풀어야 한다고 했다.

내가 제출한 코드1 (실패) - 메모리 초과

• Language : Python3

class Solution:
    def longestPalindrome(self, s: str) -> str:
        slice = sorted(s, key=len, reverse=False)
        answer = []

        for i in range(len(slice)-1):
            temp1 = slice[i]
            for j in range(i+1, len(slice)):
                temp2 = slice[j]
                if temp1 == temp2:
                    answer.append(slice[i:j+1])

        if len(answer) == 0:
            return slice[0]

        result = []

        for i in range(len(answer)):
            if answer[i] == list(reversed(answer[i])):
                result.append(answer[i])

        result.sort(key=len, reverse=True)

        if len(result) != 0:
            return ("".join(result[0]))
        return answer[0][0]

내가 제출한 코드2 (실패) - 시간 초과

• Language : Python3

class Solution:
    def longestPalindrome(self, s: str) -> str:
        slice = sorted(s, key=len, reverse=False)
        #print(slice)
        
        result = []
        for i in range(0, len(slice)):
            for j in range(len(slice)-1, i, -1):
                #print(i,j)
                if slice[i] == slice[j] and slice[i:j+1] == list(reversed(slice[i:j+1])):

                    #print(slice[i], slice[j])
                    #print(slice[i:j+1])
                    result.append("".join(slice[i:j+1]))
        result.sort(key=len, reverse=True)
        if len(result) != 0:
             return result[0]
        return slice[0]

결과

이 문제를 풀고나서 이렇게 공부하면 안된다는 것을 깨달았다. 수학으로 예를 들면, 공식 알아야 문제를 풀 수 있는 일반 학생인데, 공식을 유도해 풀 수 있는 영재 학생이 아닌 경우라면 어떻게 풀어야할까 라는 고민을 하게 됐다.

그렇다면 유형별로 어떤 방식으로 접근해야 하는지를 다 학습하고, 일단은 풀어내는 것을 연습하자라는 결론을 얻었다. 이런식으로 유형을 학습하고, 비슷한 문제를 직접 풀어내는 방법으로 진행해야겠다.

따라서 Leetcode 시리즈는 내 풀이가 올라가지 않고 앞으로는 어떻게 풀어야 할지 교재에 나온 내용을 공부하는 내용이 올라갈 것 같다.