7장 9번 ~ 12번

9번 문제

#풀이 1
class Solution:
    def threeSum(self, nums):
        print(nums)
        Sum = []
        if nums == [] :
            return nums
        elif nums is 0 :
            return None
        
        else:
            for i in range(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] ==0 and sorted([nums[i],nums[j],nums[k]]) not in Sum :
                                Sum.insert(len(Sum),sorted([nums[i],nums[j],nums[k]]))
                                                             
            return Sum
 
#풀이 2
 
class Solution:
    def threeSum(self, nums):
        results = []
        nums.sort()
        
        for i in range(len(nums) -2):
            if i>0 and nums[i]==nums[i-1]:
                continue
            left, right = i+1, len(nums) -1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum < 0:
                    left +=1
                elif sum > 0:
                    right -=1
                else:
                    results.append((nums[i],nums[left],nums[right]))
                
                    while left < right and nums[left] == nums[left+1]:
                        left +=1
                    while left < right and nums[right] == nums[right -1]:
                        right -=1
                    left +=1
                    right -=1
                   
        return results

 

10번 문제

sort() 를 해서 짝수번째값이 가져와서 더하면 그값이 파티션들의 min 값들을 더한 max 값이 된다!? -> 새로운 사실

 

#풀이 1 (280ms)
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        Sum = 0
        stack = []
        for n in range(int(len(nums)/2)):
            Sum += min(nums[2*n],nums[2*n+1])             
        return Sum
#풀이 2 (252ms)
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return  sum(sorted(nums)[::2])
 

 

 

11번 문제

#풀이1 (240ms) 
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        out = []
        p =1 
        for i in range(0,len(nums)):
            out.append(p)
            p = p * nums[i]
        p = 1
        
        for i in range(len(nums)-1,0-1,-1):
            out[i] = out[i] * p
            p = p * nums[i]
            
        return out
        

 

12번 문제

#풀이 1 (시간 초과)
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = []
        if len(prices)-1<=0:
            return 0
        
        for i in range(len(prices)-1):
            for j in range(i+1,len(prices)):
                if prices[j] - prices[i] <0 :
                    profit.append(0)
                else:
                    profit.append(prices[j] - prices[i])
                
                
        return max(sorted(profit))

 

 

#풀이2 (240ms) 
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit =0
        min_price = sys.maxsize
        
        for price in prices:
            min_price = min(min_price,price)
            profit = max(profit,price - min_price)
        
        return profit