12. Best Time to Buy and Sell Stock

리트코드

• 한 번의 거래로 낼 수 있는 최대 이익을 산출하라

1. 브루트 포스로 계산

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_price = 0
        
        for i, price in enumerate(prices):
            for j in range(i, len(prices)):
                max_price = max(prices[j] - price, max_price)
                
        return max_price

• 하지만 이 방식은 타임 아웃으로 풀리지 않는다.

2. 저점과 현재 값과의 차이 계산

• 다음과 같은 시각화는 기술 통계학(Descriptive Statistics)이라고 일컬으며 통계학에서도 매우 중요한 연구 분야 중 하나이기도 하다.

• 인덱스 1은 저점을 가리키고 있고, 인덱스 4는 고점을 가리킨다.

• 현재 값을 가리키는 포인터가 우측으로 이동하면서 이전 상태의 저점을 기준으로 가격차이를 계산하고, 만약 클 경우 최댓값을 계속 교체해나가는 형태로 O(n) 풀이가 가능하다.

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

• 최댓값이 되어야 할 profit 변수와 최솟값이 되어야 할 min_price 변수의 초깃값은 이처럼 각각 시스템의 가장 작은 값, 가장 큰 값으로 정한다. 즉, 최댓값 변수는 최솟값으로 최솟값 변수는 최댓값으로 정한다.

  • 그래야 어떤 값이 들어오든 바로 교체될 수 있기 때문이다.
  • 만약, None으로 잡아두게 되면 비교 시 타입에러(TypeError)가 발생할 수 있기 때문에 이처럼 최솟값, 최댓값은 시스템의 최댓값, 최솟값으로 설정하는게 편하다.

• 최대 이익 profit이 나중에 최종 결과로 리턴되는데, 입력값이 []인 경우, 즉 빈 배열인 경우에는 자칫 -sys.maxsize가 리턴될 수 있기 때문에 여기서는 0으로 설정한다.

  • 최댓값은 0보다는 항상 커야하기 때문이다.

• 최저점과 비교해 더 작을 경우 최솟값을 갱신하고, 현재 값과 최솟값과의 차이를 계산해 만약 더 클 경우 최댓값 profit을 계속 갱신하며넛 반복한다.

➕ 카데인 알고리즘(Kadane's Algorithm) 으로도 O(n)으로 풀이가 가능하다.

range

• range는 range(시작숫자, 종료숫자, step)의 형태로 리스트 슬라이싱과 유사합니다.

• range의 결과는 시작숫자부터 종료숫자 바로 앞 숫자까지 컬렉션을 만듭니다.

• 시작숫자와 step은 생략가능합니다.

• range는 값을 확인하기 위해서 다른 순서 있는 컬렉션으로 변환해야합니다.

>>> range(5,10)
range(5, 10)
>>> list(range(5,10))
[5, 6, 7, 8, 9]
>>> tuple(range(5,10))
(5, 6, 7, 8, 9)

• 파이썬에서 권장하지 않는 패턴

>>> s = [1, 3, 5]
>>> for i in range(len(s)):
...     print(s[i])
... 
1
3
5

• 파이썬에서 권장하는 패턴

>>> for v in s:
...     print(v)
... 
1
3
5

enumerate

• 반복문 사용 시 몇 번째 반복문인지 확인이 필요할 수 있습니다. 이때 사용합니다.

• 인덱스 번호와 컬렉션의 원소를 tuple형태로 반환합니다.

>>> t = [1, 5, 7, 33, 39, 52]
>>> for p in enumerate(t):
...     print(p)
... 
(0, 1)
(1, 5)
(2, 7)
(3, 33)
(4, 39)
(5, 52)

• tuple형태 반환을 이용하여 아래처럼 활용할 수 있습니다.

>>> for i, v in enumerate(t):
...     print("index : {}, value: {}".format(i,v))
... 
index : 0, value: 1
index : 1, value: 5
index : 2, value: 7
index : 3, value: 33
index : 4, value: 39
index : 5, value: 52