문제) 한 번의 거래로 낼 수 있는 최대 이익을 산출하라
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
▶ 입력
[ 7, 1, 5, 3, 6, 4 ]
▶ 출력
5
1일 때 사서 6일 때 파는 것이 가장 큰 이익을 얻는다.
풀이)
1. 브루트 포스
만일 첫째 날인 7일때 샀을 경우, 나올 수 있는 이익은 다음과 같다.
두번째 날 팔 경우 : 1-7 = - 6 ,
세번째 날 팔 경우 : 5-7 = -2 ,
네번째 날 팔 경우 : 3-7 = -4,
다섯번째 날 팔 경우 : 6-7 = -1 ,
여섯번째 날 팔 경우 : 4-7 = -3
이런 식으로 모든 경우의 수를 구하여 최대 이익을 계산해보자.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_price = 0
for i , price in enumerate(prices) :
for j in range(i+1 , len(prices)) :
max_price = max(max_price , prices[j] - price)
return max_price
하지만 이와 같이 브루트포스로 풀이하게 되면 time error가 발생한다.
2. 저점과 현재값 차이의 계산
시각화하여 한 번 살펴보자
현재값이 우측으로 이동하면서 저점과 차이를 계산하여 최대 이익을 산출해 낼 수 있다.
따라서 현재값 - 최저점 차이를 계산하여 계속해서 최대값을 갱신하여 풀이하면 시간 복잡도를 줄일 수 있다.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_price = 0
min_price = sys.maxsize
for i , price in enumerate(prices) :
min_price = min(min_price , price)
max_price = max(max_price , price - min_price)
return max_price
💡최댓값과 최솟값의 초깃값을 설정하는 것도 따로 기록해두었다.
https://zzoming00.tistory.com/56
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[LeetCode] - 유효한 괄호 (0) | 2023.11.15 |
---|---|
[LeetCode] - 자신을 제외한 배열의 곱 (1) | 2023.11.15 |
[LeetCode] - 배열 파티션 I (0) | 2023.11.14 |
[LeetCode] - 세 수의 합 (0) | 2023.11.14 |
[LeetCode] - 두 수의 합 (0) | 2023.11.14 |