LeetCode 122. Best Time to Buy and Sell

문제 링크

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/submissions/?envType=study-plan-v2&envId=top-interview-150

문제 해석

• pries 배열은 숫자 배열
• 무조건 한 주만 소유가능 , 당일 파고 사기 가능
• 가능한 가장 큰 Profit return

문제 해결

처음 살 가장 싼 index 를 선택
그 다음 값부터 차례대로 다음 값과 비교
-> 다음 값이 더 클시 continue
-> 다음 값이 더 작을 시 현재값 - index 후 , index 는 다음 값

슈도 코드

index = 0
sum = 0
for(i=1;i<prices.length;i++)
	if(prcies[i]<prices[index])
    	index = i;
    else
    	break
for(i=index+1;i<prices.length;i++)
	if prices[index] > prices[i]:
    	continue
	if(prices.length-1==i and prices[i]>prices[index])
    	sum += prices[i]-prices[index]
        break
    if(price[i+1]<price[i] and price[i]>price[index])
    	sum +=price[i]
        index = i+1
retunr sum
     

• [0] 마지막 과 index 도 비교하므로 , 끝까지 Checking

결과

---

추가 수정

Beats %를 보고 , 내가 뭔가 비효율적이게 푼 것을 깨닫고 다시 생각하고 풀었다.
나는 당일에 팔고 그날 사는게 안되는 줄 알고 , index 를 다음 값으로 하고 , 가장 큰 경우를 생각해서 조건문을 걸었다.
동시에 사고 파는게 가능하므로 , 최소 index 를 찾을 필요도 + index 저장할 필요도 없다.

슈도 코드

for(i=0;i<prices.length-1;i++)
	if(prices[i]<prices[i+1])
    	sum+= prices[i+1]-prices[i]

결과

사담

처음 문제를 보고 해석하고 생각할 때 , 완전 생각을 잘못하고 빙빙 둘러간 느낌이다. 단순히 코드에 넘어갈 생각을 하지 말고 , 더욱 최적화 할 방법은 없는지 & 내가 너무 어렵게 생각하고 있는건 아닌지 잘 생각해봐야 하는거 같다.

메모본