Algorithm Study/leetcode
[LeetCode] 121. 주식을 사고팔기 좋은 시점(Best Time to Buy and Sell Stock
오패산개구리
2021. 6. 29. 15:37
728x90
반응형
한 번의 거래로 낼 수 있는 최대 이익을 산출하라.
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation:
Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
1. 내가 직접 푼 코드
|
1
2
3
4
5
6
7
|
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = []
for i in range(len(prices)-1):
max_profit.append(max(prices[i+1:]) - prices[i])
print(max_profit)
return max(max_profit)
|
cs |
해설:
for문을 돌리면서 현재 인덱스와 그 뒤 인덱스들의 차가 제일 큰 값을 리스트에 넣었다.
그 후 그 리스트에서 제일 큰 값을 뽑아낸다.
나름 괜찮은 풀이 같아서 알아보니 런타임 에러가 뜨더라...
시간 복잡도가 O(n^2)이 넘어간다는 뜻인데
슬라이싱 한 것에 max를 취한 것이 아마 런타임 에러의 문제인 듯싶다.
** 깔끔 답안 **
2. 저점과 현재 값과의 차이 계산
|
1
2
3
4
5
6
7
8
9
10
11
|
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
|
cs |
해설:
for문으로 진행하면서 최솟값이 되는 가격을 따로 저장해 두고
최소 가격과 현재 가격 간의 차이에 max를 취해 profit에 저장한다.
이런 식으로 하면 O(n)에 해결할 수 있어서 런타임 에러가 뜨지 않는다!
만약 쉽게 알고리즘이 떠오르지 않는다면 그래프로 한 번 그려보자.
값을 시각화해보면 어떤 식으로 풀어야 할지 직관이 생긴다고 한다.
출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]
728x90
반응형