배열

https://leetcode.com/problems/trapping-rain-water/

'''
    높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산
    Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
    Output: 6

    방법1)
        최대 높이 - 현재 높이 = 물이 고인 양

    방법2)
        현재 높이가 이전 높이 보다 높을 때 

'''
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        #양쪽에서 시작하여 최대높이 까지
        volume = 0
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]


        #좌우가 만날때 종료
        while left < right:
            #좌우 최대값 입력
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)

            #좌우 높은 쪽으로 이동하므로,오른쪽이 크면 왼쪽이 이동, 왼쪽이 크면 오른쪽이 이동 
            #따라서 최대 지점에서 만나게됨
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
        return volume

https://leetcode.com/problems/3sum

'''
배열을 입력받아 합으로 0을 만들 수 있는 3개의 요소를 출력하라
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

방법1)
두요소의 합*(-1) 에 해당되는 값이 있는지 확인한다.
-1 => [0, 1, 2, -1, -4]
=> 모든 요소를 다 더해봐야함 = n^3

방법2)
정렬을 한 뒤 비교(투포인터 방식으로 비교) => nlog(n) + n^2
1. 정렬
2. 기준점을 둠, 나머진 투포인터 방식으로 비교(left, right지정)
3. 중복값이 있을경우 넘어감(계산낭비)

'''

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result=[]
        #1.정렬
        nums.sort()

        #2.기준값 두고 비교(마지막 값 2개는 사용하지 않음)
        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:
                    result.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 result

https://leetcode.com/problems/array-partition-i/

'''
n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.
Input: nums = [1,4,3,2]
Output: 4

Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

방법1) 
정렬한 뒤, 뒤에서부터 2개씩 묶어 계산 = nlogn

방법2)
짝수번째 값이 항상 min값이 됨

방법3)
슬라이싱 사용

'''
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        '''
        nums.sort()
        result = 0
        pair = []
        '''

        '''
        =====================================================
        방법 1)
        =====================================================
        '''
        '''
        387ms = 속도 더 나음
        for i in range(len(nums)-1, 0, -2):
            #배열의 개수가 홀수인 경우
            if i != 0:
                result += min(nums[i], nums[i-1])
        '''


        '''
        514ms = 가독성 좋음
        for n in nums:
            pair.append(n)
            if len(pair) == 2:
                result += min(pair)
                pair = []
        '''

        '''
        =====================================================
        방법2) 276ms
        =====================================================
        '''
        '''
        if len(nums)%2 == 0:
            for i, n in enumerate(nums):
                if i%2 == 0:
                    result += n
        else:
            for i, n in enumerate(nums):
                if i%2 != 0:
                    result += n

        return result
        '''

        '''
        =====================================================
        방법3) 314ms
        =====================================================
        return sum(sorted(nums)[::2])
        '''

https://leetcode.com/problems/product-of-array-except-self/

'''
배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라.
단 나눗셈을 하지 않고 O(n) 에 풀어라

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

방법1)
자기자신 제외하고 나머지 값들 곱함
자기 자신 제외하고 왼쪽 오른쪽 구분하여 서로 곱함

1 2 3 4

1. 1*(2*3*4)
2. (1)*(3*4)
3. (1*2)*(4)
4. (1*2*3)*1

왼쪽 1, 1, 2, 6
오른쪽 24, 12, 4, 1


'''

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = []
        tmp = 1

        #왼쪽
        for i in range(len(nums)):
            result.append(tmp)
            tmp = tmp * nums[i]

        tmp = 1
        #오른쪽 => 반대로
        for i in range(len(nums)-1, -1, -1):
            result[i] = result[i] * tmp
            tmp = tmp * nums[i]

        return result

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

'''
주식을 사고팔기 가장 좋은 시점

한번의 거래로 낼 수 있는 최대 이익을 산출하라.
Input: prices = [7,1,5,3,6,4]
Output: 5
2일날 1에 사서 5일날 6에 팔면 최대의 이익이다.

방법1)
현재 값보다 다음값이 크면, 현재 이후의 값중 최대값을 구하여 이익을 계산 => 예시의 경우 
1->5, 3->6 두가지의 경우를 계산해야한다.

방법2) 방법1 복잡도 줄여야
최소값과 최대 이익값을 갱신하면서 마지막에 차이를 구함


'''


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        '''
        방법1) 시간 초과남
        max_profit = -1
        profit = 0

        leng = len(prices)

        for i in range(leng):
            if i < leng-1 and prices[i] < prices[i+1]:
                profit = max(prices[i:]) - prices[i]

            if max_profit < profit:
                max_profit = profit
        '''

        profit = -sys.maxsize-1
        min_price =  sys.maxsize

        #갱신
        for i in range(len(prices)):
            min_price = min(min_price, prices[i])
            profit = max(profit, prices[i]-min_price)

        return profit