[Leetcode Top Interview 150] 122. Best Time to Buy and Sell Stock II

난이도 : medium

문제링크

• int 배열인 prices가 주어진다
• i인덱스 값은 i날짜의 상품가격이다
• 날마다 사거나 팔수 있음
  • 하루에 최대 하나만 보유할 수 있음
  • 구매한 날에 즉시 판매 가능
• 최대 이익을 리턴하라

 

1. 접근법

• 이익을 볼 수 있는 거래가 많을수록 최대 이익을 얻을 수 있다
• 저점에 사서 고점에 파는 전략을 선택한다
• 그리디 알고리즘을 활용하여 풀 수 있다

 

2. 의사코드

public int maxProfit(int[] prices) {                
    int maxProfit = 0;
    int curIdx = prices.length-1, prevIdx = curIdx-1;

	// 뒤에서부터 조회 : 판매 날짜에 대한 저점 매수 날을 찾는다 (모든 배열 탐색할 때까지)
    while (curIdx > 0) {  
        // 만약, 어제 구매날짜가 오늘보다 더 낮다면
        // 반복하면서 직전날짜보다 저점 가격의 날짜를 찾는다
        // 구매가격 - 저점 매수가격을 최종값에 더한다        
    }

    return maxProfit;
}

 

3. 구현 코드

public int maxProfit(int[] prices) {                
    int maxProfit = 0;
    int curIdx = prices.length-1, prevIdx = curIdx-1;

    while (curIdx > 0) {            
        if (prices[curIdx] > prices[prevIdx]) {
            while (prevIdx > 0 && prices[prevIdx] > prices[prevIdx-1]) {
                prevIdx--;
            }
            maxProfit += prices[curIdx] - prices[prevIdx]; 
        }     

        curIdx = prevIdx;
        prevIdx = curIdx-1;             
    }

    return maxProfit;
}

 

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 요소를 순회함
• 공간복잡도 : O(1) - 상수 데이터만 메모리 사용함