[1주차] 122. Best Time to Buy and Sell Stock II

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

Best Time to Buy and Sell Stock II - LeetCode

---

📝 문제

정수 1차원 배열이 주어진다. 배열의 인덱스는 주식의 날짜이며, 원소는 가격이다. 매일 주식사거나 팔 수 있으며 주식은 한 주만 보유가능하다.

주식을 사고팔아 얻을 수 있는 가장 큰 이득을 리턴하라. 단, 주식을 산 날에 즉시 팔 수 있다.

 

🎈 풀이

주식 1 문제를 해결하지 못했기 때문에 이전 문제에서 얻은 지식을 동원하여 최대한 혼자서 풀어보려고 노력했다.

원소를 단순화하여 생각 해 보았다.

 

1. 주식이 꾸준히 우하향 중 이라면? - [5, 4, 3, 2, 1]

이 경우 매수 타이밍을 잡을 수 없다. 배열이 내림차순 정렬이기 때문에 수익을 절대로 낼 수 없는 상황이다.

 

2. 주식이 꾸준히 우상향 중 이라면? - [1, 2, 3, 4, 5]

이 경우는 주식을 최대한 팔지 말고 가지고 있어야 한다. 만약, 1에 사고 2에판매, 3에 사고 4에 판매 등, 수익을 낼 수 있을 때 바로바로 팔아버리는 방식을 사용하면, 1에 사서 5에 파는 것 보다 수익이 낮다. (2-1) + (4-3) < (5-1)

 

3. 주식이 우하향하다가 중간에 반등한다면? - [5, 3, 1, 3, 5]

이 배열은 0~2 인덱스까지는 1번의 우하향 형태이고, 인덱스 2~마지막 까지는 2번의 우상향 형태이다.

따라서, 우하향 중일 때는 주식을 사지 말고, 반등할 타이밍에 사고, 계속 우상향한다면 가지고 있어야 한다.

 

여기까지 도달하고 보니 처음에는 보이지 않았던 로직이 보이기 시작했다.

 

나는 주식의 내일 가격을 알 수 있는 능력자다

• 난 현재 주식을 가지고 있다.
  • 내일 주식이 오른다. 오늘 파는 것 보다는 내일 파는게 이득이니 존버하자.
  • 내일 주식이 떨어진다. 오늘 팔고 내일 또 사면 이득이다.

 

• 난 현재 주식을 가지고 있지 않다.
  • 내일 주식이 오른다. 오늘 사야지 수익실현을 할 수 있다.
  • 내일 주식이 떨어진다. 오늘 사는것 보다는 내일 사는게 이득이므로 기다리자

 

 

fun maxProfit(prices: IntArray): Int {
    var stock = -1
    var profit = 0
    for (i in 0 until prices.lastIndex) {
        if (prices[i] > prices[i+1]) {
            // 내일 주식이 오늘보다 떨어진다.
            // 주식을 보유중이면 팔아야하고 없으면 가만히 있자
            if (stock != -1) {
                profit += prices[i] - stock
                stock = -1
            }
        } else if (prices[i] < prices[i+1]) {
            // 내일 주식이 오늘보다 오른다.
            // 주식을 보유중이면 더 오를 수 있으니 존버하고 없으면 사자
            if (stock == -1) {
                stock = prices[i]
            }
        }
    }

    if (stock != -1) profit += prices.last() - stock

    return profit
}

• stock 에는 내가 과거 어떤 날짜에 주식을 산 가격을 저장한다.
• 주식 가격 범위가 0 <= stock <= 10^4 이므로 주식을 현재 보유하지 않았으면 -1 상태인 것으로 정의한다.

 

배열이 중간부터 오름차순이 되어서 끝나면 주식을 팔지 못하게 된다. 따라서 마지막에 주식을 가지고 있으면 마지막날에 팔아버린다.

만약 마지막날에 주식을 구매하였다면? 동일 날 매수 매도를 동시에 할 수 있으므로 상관 없다.

문제의 However, you can buy it then immediately sell it on the same day. 조건은 이걸 위한 내용이었던 것 같다.