[코테] Best Time to Buy and Sell Stock

문제링크

Best Time to Buy and Sell Stock - LeetCode

<로직 고민/>

• 일단 buy, sell, profit 이라는 변수를 생성하고, buy는 prices 배열의 첫 번째 값, sell과 profit은 0으로 초기화한다
• for문을 prices 인덱스 0부터 마지막 인덱스 전까지 돌린다
• 0번 인덱스 값부터 비교해서, 해당 값이 buy 값보다 작으면 buy에 해당 값을 넣는다(적은 돈으로 살 수록 이익이 크니까)
• 그렇게 수정된 buy 값과 다음 인덱스 값과 비교해서 buy보다 크면 sell에 다음 인덱스 값을 넣는다(산 값보다 판 값이 더 커야 이익이니까)
• 그 다음 profit과 sell - buy 연산의 값을 비교해서 sell - buy 연산 값이 더 크면 profit에 해당 값을 넣는다
• 다음 for문이 돌기 전, sell은 0으로 초기화 해준다(계속해서 바뀔지 모르는 buy 값과 비교해서 sell 값을 업데이트 해줘야 하기 때문)

---

<완성된 풀이/>

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy, sell, profit = prices[0], 0, 0

        for i in range(len(prices)-1):
            if prices[i] < buy:
                buy = prices[i]
                
            if buy < prices[i+1]:
                sell = prices[i+1]
                
            if profit < sell - buy:
                profit = sell - buy
                
            sell = 0
            
        return profit

• 꽤 괜찮은 점수같긴 한데 시간복잡도를 조금 낮춰야 할 필요가 있어보인다

---

<다른 사람 풀이/>

- 천재풀이1

def maxProfit(self, prices: List[int]) -> int:
	if not prices:
		return 0

	maxProfit = 0
	minPurchase = prices[0]
	for i in range(1, len(prices)):		
		maxProfit = max(maxProfit, prices[i] - minPurchase)
		minPurchase = min(minPurchase, prices[i])
	return maxProfit

• 아 if문으로 할 게 아니라 max, min함수 썼으면 됐구나...!!
• 근데 max, min 쓰니까 실행시간이 더 걸린다

# 위 코드 보고 수정한 풀이
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy, sell, profit = prices[0], 0, 0

        for i in range(len(prices)-1):
            buy = min(prices[i], buy)
            sell = max(prices[i+1], buy)
            profit = max(profit, sell - buy)
            sell = 0
            
        return profit

• 뭔가 보기엔 깔끔해 보여서 좋긴 한데...