[Easy] LeetCode - no.121 Best Time to Buy and Sell Stock ⭐ : Java

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

주식을 구매할 날을 고르고, 미래의 다른 날에 팔았을 경우 얻을 수 있는 최대 수익을 반환할 것

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.

 

 

 

풀이

첫 시도

• 예시 : [7, 1, 5, 3, 6, 4]
• [7, 1] 과 같이 가격이 하락하는 경우 뒤의 숫자를 기준으로 그 뒤의 가격들 [5, 3, 6, 4] 중 가장 큰 가격과의 차를 계산하여 그 중 가장 큰 값을 리턴
• 잘못된 부분 : [1, 2, 4] 와 같이 가격이 계속해서 상승하는 경우를 고려하지 못함

 

 

풀이 참조 후 재시도

class Solution {
    public int maxProfit(int[] prices) {
        int buyPrice = prices[0];
        int profit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (buyPrice > prices[i]) {
                buyPrice = prices[i];
            }

            profit = Math.max(profit, prices[i] - buyPrice);
        }

        return profit;
    }
}

• prices[0]의 가격을 buyPrice로 지정
• i = 1부터 for문을 순회하며 buyPrice보다 낮은 가격이 나오면 buyPrice를 대체함
• Math.max()를 사용하여 prices[i] - buyPrice를 계산한 값 중 가장 큰 값을 리턴함
• 시간복잡도 : O(N)