[배열] 12 주식을 사고팔기 가장 좋은 시점(Best Time to Buy and Sell Stock)

<LeetCode 문제>

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

Best Time to Buy and Sell Stock - LeetCode

한 번의 거래로 낼 수 있는 최대 이익을 산출하는 문제입니다.

<풀이>

이 문제는 N이 최대 10⁵이므로 브루트포스를 통한 O(N²)으로는 풀 수 없습니다.

처음 풀이한 코드는 다음과 같습니다. 가격의 최저점을 갱신해나가고, 최저점보다 가격이 높다면 시세차익을 계산해 기존의 시세차익보다 크면 갱신합니다. 이는 시간복잡도 O(N)으로 시간초과에 걸리지 않습니다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        minimum = 10**5 #가격 최소값
        result = 0 #시세차익 최대값
        
        for price in prices:
            if minimum > price:
                minimum = price #현재 price가 minimum보다 작으면 갱신
            
            if minimum < price: #현재 price가 minumum보다 크면
                result = max(result,price-minimum) #시세차익 구해서 기존보다 크면 갱신
                
        return result

 

코드를 깔끔하게 정리하면 다음과 같습니다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        minimum = sys.maxsize #가격 최소값
        result = 0 #시세차익 최대값
        
        for price in prices:
            minimum = min(minimum,price) #현재 price가 minimum보다 작으면 갱신
            result = max(result,price-minimum) #시세차익 구해서 기존보다 크면 갱신
                
        return result

 

이 문제는 '최대 서브 배열'문제에서 전체 합이 아닌 저점과 고점의 차이 값이라는 정도만 다를 뿐, 거의 동일한 유형의 문제입니다. 여기서도 카데인 알고리즘을 응용해 O(N)에 풀이했습니다.

<학습내용>

1. 최댓값에 가장 낮은 값, 최솟값에 가장 높은 값을 초깃값으로 할 때, sys.maxsize, -sys.maxsize 이용.
(float('inf'), float('-inf')로 무한대값을 지정할 수도 있다)

<학습이 필요한 내용>

1. 최대 서브 배열 풀어보기(카데인 알고리즘 학습)

 

https://github.com/HoYoungChun/Algorithm_PS/blob/master/Python_Study/07_array/LC_121.py

GitHub - HoYoungChun/Algorithm_PS: Baekjoon Online Judge, Programmers, LeetCode problem solving by Python, C++