[LeetCode] 121. Best Time to Buy and Sell Stock

---

문제

 

leetcode.com/problems/best-time-to-buy-and-sell-stock/

---

풀이

 

사실 쉽다. 쉬운 문제인데, 난 항상 처음 생각을 하는 방식이 잘못됐다고 본다.

무조건 for문이 나오고 결국 2중 for문을 썼고, 시간복잡도를 늘려놓는 바람에 통과하지 못했다.

이게 dp인가? 라는 생각을 하긴 했지만

결국 제일 많은 추천을 받은 문제는 dp와 비슷하게 풀더라. 하지만 브루트포스였다.

 

    buy = prices[0]	//처음 물건을 사는걸로 시작. 
    mx_profit = 0	//최종 정답이 될 이 값에 큰 값을 비교해 바꿔주는 형식.
    
	for i in range(1,len(prices)):
        profit = prices[i]-buy	//이익은 산 값의 다음 값(초기값을 prices[0]으로 했기 때문) - 산 값
    
        if profit>mx_profit:	//이익이 맥스 이익보다 크다면
            mx_profit = profit	//이익을 맥스이익에 대입
        
        if buy>prices[i]:	//현재 가격이 산 가격보다 작으면 손해니까
            buy = prices[i]	//현재 가격을 산 가격으로
    
    return mx_profit

 

많이 문제를 풀어보라고 하는 이유를 알겠다.

dp일까? 라고 생각하는 순간 내가 그래도 성장했음을 느껴서 뿌듯했다.