“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
주어진 배열은 주식 가격의 리스트를 나타내고 한 번의 거래로 낼 수 있는 최대 이익을 찾는 문제다. 입력이 [7,1,5,3,6,4]일 경우 최대 이익은 1에 사서 6에 파는 경우이므로 5가 된다.
그냥 브루트 포스로 풀면 쉽지만 복잡도가 O(n^2)이므로 그대로 제출하면 타임아웃이 발생한다. 애시당초 그렇게 쉽게 놔둘 리가 없지. 그래서 O(n)에 풀이하도록 요구하는 듯 하다.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 1.blute force
# max_price = 0
# for i,price in enumerate(prices):
# for j in range(i, len(prices)):
# max_price = max(max_price, prices[j] - price)
# return max_price
# 2.
profit = 0
min_price = sys.maxsize
for price in prices:
min_price = min(min_price, price)
profit = max(profit, price - min_price)
return profit- 순서대로 탐색하면서 최저점을 추적한다.(min_price)
- 각 값들과 최저점을 비교해서 최대 이익을 갱신한다.
최소, 최고값을 지정하는 방법을 배울 수 있었다. 위에서는 시스템이 지정할 수 있는 최대값인 sys.maxsize를 사용했다. 사실상 무한대의 값을 지정할 수 있는 파이썬에서는 의미가 없다고는 하지만 애매하게 999999와 같은 숫자를 지정하면 낭패를 볼 수 있다. 퀴즈 같은 경우에는 최대, 최소값을 명확히 알려주니까 그걸 간과해서는 안 되겠다.