[LeetCode/Kotlin]Easy - 121. Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock - LeetCode

문제

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

풀이

나의 최종 풀이

풀이 접근 과정

처음엔 모든 숫자를 순회를 돌며 j-i 값을 구해서 그 값이 큰 경우를 계산을 했다.

그런데 시간 초과가 났다.

이건 이중 반복문이 아니라 반복문 한 번으로 끝내는 문제였다.

이중 반복문을 했던 이유가 앞서 주식 가격을 계산한게 뒤에서 계산한 것보다 작은 경우가 있지 않을까? 해서였다.

예를 들어 2에서 사서 8에서 팔았는데, 뒤에 최솟값이 다시 1로 떨어지고 8에서 팔면?

근데 생각해보 그냥 그건 최솟값만 갱신하고 계산만 하면 되는 거였다… ㅎㅎㅎㅎ

그래서 반복문 한번으로 충분히 해결되는 문제였다.

내가 너무 복잡하게 생각해서 돌아가버린….ㅎㅎ

최종 소스코드

1. answer와 min이라는 두 변수를 초기화한다.
2. prices.indices를 통해 가격 배열의 인덱스를 순회한다.
3. 현재 가격(prices[i])이 최솟값(min)보다 작으면 최솟값을 현재 가격으로 업데이트한다. 최솟값은 배열에서 이전까지의 가격 중 가장 작은 값을 유지한다.
4. 현재 가격에서 최솟값을 뺀 값(prices[i]-min)이 현재까지의 최대 이익(answer)보다 크면 최대 이익을 해당 값으로 업데이트한다. 이익은 이전까지의 최대 이익 중 가장 큰 값을 유지한다.
5. 배열 순회가 끝나면 최대 이익(answer)을 반환한다.

class Solution {
    fun maxProfit(prices: IntArray): Int {
        var answer = 0
        var min = Int.MAX_VALUE

        for (i in prices.indices) {
            if (prices[i] < min) min = prices[i]
            if (prices[i]-min > answer) answer = prices[i]-min
        }

        return answer
    }
}