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

https://leetcode.com/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150

Jump Game - LeetCode

---

📝 문제

정수 1차원 배열이 주어진다. 배열의 인덱스는 주식의 날짜이며, 원소는 가격이다. 주식을 사고 팔아 얻을 수 있는 가장 큰 수익을 리턴하라. 단, 주식은 과거 날짜로 팔 수 없으며 단 한번만 사고 팔 수 있다.

 

🎈 풀이

수 시간에 걸쳐 고민하였으나 결국 해답을 얻지 못했다.

어떻게 해도 모든 경우의 수를 모두 따져서 수익을 얻는 방식밖에 떠오르지 않았다. O(n^2) 시간복잡도를 가지기 때문에 최대 n이 100,000 인 해당 문제에선 시간초과가 나온다.

 

📈 타 솔루션 참고

투 포인터를 이용하여 O(n) 시간에 푸는 알고리즘이다.

fun maxProfit(prices: IntArray): Int {
    var buy = 0
    var sell = 1
    var maxProfit = 0
    while (buy in prices.indices && sell in prices.indices) {
        if (prices[buy] < prices[sell]) {
            maxProfit = max(maxProfit, prices[sell] - prices[buy])
            sell++
        } else {
            buy = sell
            sell++
        }
    }

    return maxProfit
}

 

문제를 푸는 키는 현재 원소보다 다음에 나올 원소의 값이 작을 때이다.

더 작은 원소를 만나는 순간 이전 인덱스에 위치한 원소는 신경쓸 필요가 없어진다. 더 작은 원소에서 사는게 어떻게 해도 큰 이득을 얻을 수 밖에 없기 때문이다.

 

예를 들어, [4, 100, 1, 5, 2] 이라는 배열이 있다고 하자.

4 가격에 사서 파는 수익을 모두 얻는 다고 가정할 때, 얻을 수 있는 수익은 [96, -3, 1, -2] 이다.

하지만 탐색 과정에서 4 보다 작은 1을 만났다. 주식은 과거 날짜로 팔 수 없기 때문에 1을 만나는 순간 이후에 존재하는 [5, 2] 가격에 팔 때에는 4 가격에 사는 것 보다는 1에 사는 것이 무조건 이득이다.

1에 사서 파는 이후 주식은 [4, 1] 수익으로 4에 팔아 얻는 [1, -2] 수익보다는 반드시 커지게 된다.

따라서 96 수익을 기록한 후에 1을 만나면 더 이상 4 가격에 샀을 때의 수익은 구할 필요가 없어진다.

남은 연산은 1에 사서 이후에 파는 연산만이 남아있게 된다.

 

따라서 투 포인터를 사용한다. 

• buy 포인터는 주식을 구매하는 날짜를 가리키는 포인터이다.
• sell 포인터는 주식을 판매하는 날짜를 가리키는 포인터이다.
• buy에 사서 sell에 수익을 얻을 수 있으면 현재 얻은 큰 수익과 비교하여 교체한다.
• 수익을 얻을  수 없다면, 이후 주식은 현재 buy에 사는 것 보다. sell 에 위치한 주식을 사는게 무조건 이득이게 된다.
• 따라서 buy 포인터를 sell 포인터 위치로 이동하고, sell은 그 다음 날짜를 가리킨다.