주식을 사고팔 때의 최대 수익을 계산하는 문제이다.
[7, 1, 5, 3, 6, 4]의 예제에서는 가장 낮은 가격인 1에 사고 높은 가격인 6에 팔면 최대 수익이 5가 된다.
이때 판매한 날의 가격 인덱스는 구매한 날의 가격보다 무조건 높아야 하며, 만약 배열의 원소들이 점점 줄어드는 형태의 가격정보라면(ex. [5, 4, 3, 2, 1]) 최대 수익은 0이다.
풀이
나의 풀이
class Solution:
def maxProfit(self, prices: List[int]) -> int:
buy = prices[0]
profit = 0
for price in prices[1:]:
if buy > price:
buy = price
profit = max(profit, price - buy)
return profit
buy(구매 가격)을 첫날 가격으로 초기화하고, profit(수익)은 0으로 초기화한다.
prices[1:]부터 반복문을 돌리는데, 이때 [1:]의 의미는 인덱스 1부터 시작한다는 뜻이다.
내가 구매한 가격보다 작은 수라면 buy를 작은 수로 변경한다.
그리고 수익은 price(오늘의 가격)에서 buy(구매한 가격)을 빼서 기존의 수익가격과 비교한 뒤 최댓값으로 변경한다.
이때 오늘의 가격이 구매 가격이라면 price - buy가 0이 되므로 수익은 변하지 않게 된다.
책의 풀이
class Solution:
def maxProfit2(self, prices: List[int]) -> int:
buy = sys.maxsize
profit = 0
for price in prices:
buy = min(buy, price)
profit = max(profit, price - buy)
return profit
나의 풀이랑 크게 다른 점은 없지만 러닝타임은 더 오래 걸렸다.(오래라고 하지만 해봤자 80ms)
먼저 구매 가격을 sys.maxsize로 두어서 시스템의 가장 큰 값으로 정한 뒤에, 반복문에서 min()함수로 buy(구매 가격)을 정하였다.
'멋진 개발자 > 알고리즘' 카테고리의 다른 글
LeetCode 21. Merge Two Sorted Lists (0) | 2024.06.03 |
---|---|
LeetCode 234. Palindrome Linked List (0) | 2024.05.30 |
LeetCode 238. Product of Array Except Self (0) | 2024.05.28 |
LeetCode 561. Array Partition (0) | 2024.05.27 |
LeetCode 42. Trapping Rain Water (0) | 2024.05.24 |