[코테] 리트코드 파이썬 5번, 15번 - 시간초과 해결

5. Longest Palindromic Substring

Longest Palindromic Substring - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

문자열에서 가장 긴 palindromic(앞에서 읽으나 뒤에서 읽으나 동일한) substring을 찾는 문제이다.

 

첫 시도에서는 주어진 문자열을 이중반복문을 사용하여 모든 substring을 알아낸 후에, 해당 substing이 palindromic한지 알아내는 함수를 통해 확인하였다. 만약 조건을 만족한다면 stacks에 저장하였고, max(stacks,key=len)의 param을 통해 문자열의 길이를 최대값으로 알아냈다.

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        stacks=[]
        def check(s:str) -> bool:
            if len(s)%2==0:
                array1=s[:len(s)//2]
                array2=s[len(s)//2:]
            else:
                array1=s[:len(s)//2]
                array2=s[len(s)//2+1:]
            array1=array1[::-1]
            if array1==array2:
                return True
            else:
                return False

        for i in range(len(s)):
            for j in range(i+1,len(s)+1):
                if check(''.join(s[i:j])):
                    stacks.append(''.join(s[i:j]))
        
        return max(stacks,key=len)

 

하지만 이와 같은 방식은 palindrom인지 확인하는 과정에 시간초과가 난다. 반복문을 사용하는 과정에서 substring을 구하는 방식을 사용하면 시간초과없이 해결할 수 있다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s
        
        Max_Len=1
        Max_Str=s[0]
        for i in range(len(s)-1):
            for j in range(i+1,len(s)):
                if j-i+1 > Max_Len and s[i:j+1] == s[i:j+1][::-1]:
                    Max_Len = j-i+1
                    Max_Str = s[i:j+1]

        return Max_Str

---

15. 3Sum

3Sum - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

주어진 정수리스트에서 세 원소의 합이 0이면서, 세 원소의 value가 모두 다른 정수리스트를 찾는 문제이다.

 

이중반복문을 사용하여 두 원소의 합을 계산하여, 0이 될 수 있는 다른 원소의 value가 정수리스트에 있는지 확인하였다. 있다면 결과리스트에 세 원소의 value를 저장하고, 세 원소의 value가 모두 다른 것을 확인하기 위해 세 원소를 set으로 구성하여 confirm으로 따로 저장했다. 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        array=[]
        confirm=[]
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i!=j:
                    check=-(nums[i]+nums[j])
                    if check in nums:
                        k=nums.index(check)
                        if j!=k and i!=k and {nums[i],nums[j],nums[k]} not in confirm:
                            array.append([nums[i],nums[j],nums[k]])
                            confirm.append({nums[i],nums[j],nums[k]})
        
        return array

 

두 원소의 합을 통해 합이 0이되는 조건을 만족하는 다른 원소를 찾는 방식은 시간초과로 통과하지 못했다. 주어진 정수리스트를 정렬하여 세원소의 합이 0이되는 것을 두 포인터를 사용하여 겹치는 원소없이 확인한다면 시간초과를 피할 수 있다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans=set()
        nums.sort()
        n=len(nums)
        for i in range(n-2):
            j=i+1
            k=n-1
            while j<k:
                temp=nums[i]+nums[j]+nums[k]
                if temp==0:
                    ans.add((nums[i],nums[j],nums[k]))
                    j+=1
                elif temp>0:
                    k-=1
                else:
                    j+=1
        return ans