[LeetCode] 122. Best Time to Buy and Sell Stock II

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

개요

1. i번째 날짜에 대한 주가가 배열로 주어진다.
2. 최대 이익을 찾아라.
   • 이익이 누적된다.
   • 매수 이후 매도가 된 후 다음 매수가 이루어질 수 있다.
     • 매수-매수나 매도-매도는 불가함.
     • 구매하고 즉시 매도 가능하다.
   • 이익을 얻을 수 없다면 0을 리턴해라.

문제 해결 아이디어

1. 매수일과 매도일은 각각 매도 구간 내 최소, 최대인 시점이다.
   --
2. (가정) 매수 - 매도 횟수가 최대일 때 이익이 가장 크다.

• 위 가정을 매도 구간이 두개 일때 얻을 수 있는 이익이 최소인 케이스로 검증해보자
  ➡️ 이 케이스에서 최대 매도를 두 번 할 수 있다.
  ➡️ 3번의 값과 4번의 값의 차이가 최소 = 매도 구간이 두 개 일 때 얻을 수 있는 이익이 최소
  
  • 매도 구간이 한개 일때 이익 : 4 - 1 = 3
  • 매도 구간이 두개 일때 이익 : (3 - 1) + (4 - 2) = 4

🧐 최대한 많이 매도 구간을 만들자

➡️ 매도 구간이 최소 크기라면, 오름차순인 구간은 무조건 매도 구간이다.
➡️ 내림차순일 때 매도 구간은 끝난다. 따라서 이 때 매도 구간의 이익을 계산하자.

의사 코드

1. 주가 배열을 돌며 최소 주가를 찾는다.
   1-1. 이전값과 현재값의 관계가 내림차순인가?
   1-1-1. 현재 매도 구간의 이익을 계산한다.
   1-1-2. 전체 이익에 현재 이익을 더한다.
   1-1-3. 최소 주가를 갱신한다.
   1-1-4. 최대 주가를 초기화한다.
2. 주가 배열을 돌며 구간 내 최대 주가를 찾는다.

for(주가:주가 배열){
	if(이전값 > 현재값){
		현재 이익 = 최대 주가 - 최소 주가
		전체 이익 = 전체 이익 + 현재 이익 
        최소 주가 = 현재값
        최대 주가 = 0
    }
    이전값 = 현재값
    if(주가 > 최대 주가){ 최대 주가 = 주가 }
}
return 전체 이익

결과

전체 코드 github 링크

다른 풀이

public int maxProfit(int[] prices) {
        int profit=0;
        for(int i=1; i<prices.length; i++){
            if(prices[i]>prices[i-1]){
                profit+=prices[i]-prices[i-1];
            }
        }
        return profit;
    }

내림차순일 때 무조건 매도 구간이 갱신되기 때문에, 매도 구간의 마지막 값이 가장 큰 값이 된다.
따라서 굳이 매도 구간의 max 값을 추산할 필요가 없다.
또한 오름차순은 순차적 증가하기 때문에, 위 코드처럼 오름차순 구간내 요소 간 값의 차이를 profit에 계속 더해주는 방식으로 값을 구할 수 있다.

나는 오름차순이라는 점만 생각했지, 오름차순의 특징을 활용하지 못해 코드가 매우 복잡한데 위 코드는 오름차순의 특징 또한 활용해서 보다 간결하게 코드를 작성했다.
문제를 풀 때 조금 더 숨겨진 규칙에 대해 고민해보아야겠다.

ex>
[1 4 6 7 9]

[1 1+3 1+3+2 1+3+2+1 1+3+2+1+2]