[Leetcode] 시간복잡도 개선 사례

• 1 5
• -231 31 - 1

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        # 3개가 증가패턴이면 true, 아니면 false
        for i in range(0, len(nums)-2):
            for j in range(i+1, len(nums)-1):
                for k in range(j+1, len(nums)):
                    if nums[i]<nums[j]<nums[k]:
                        return True
        return False
                
        

효과적인 greedy

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = float('inf') # 가장 작은 값
        second = float('inf') # 두 번째로 작은 값

        for num in nums:
            if num <&#x3D; first:
                first &#x3D; num # 더 작은 첫 번째 값 발견
            elif num <&#x3D; second:
                second &#x3D; num # 더 작은 두 번째 값 발견
            else:
                return True # first < second < num 발견!
        
        return False
        

• 2 5
• -30
• The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n

        # 왼쪽에서 오른쪽으로 prefix 곱
        for i in range(1, n):
            answer[i] = answer[i-1] * nums[i-1]
        
        # 오른쪽에서 왼쪽으로 suffix 곱
        suffix = 1
        for i in range(n-1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]

        return answer