[LeetCode] 121번 (Best Time to Buy and Sell Stock)

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

Majority Element - LeetCode

---

🤣 문제 설명

• 주식의 일 가격이 나열되어 있는 정수 배열 prices 가 주어진다.
• 주식을 가격에 사서 최소 다음 날 가격에 팔 수 있다고 가정했을 때, 얻을 수 있는 가장 큰 이익을 구해 반환하여라.
• 단 이익을 얻을 수 없을 시에는 0을 반환한다.
• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

 

🥲 문제 해결

• 첫 번째날 가격을 current 변수에 저장하고, 반복문을 돌아 prices 에 접근한다.
• price 가격에서 현재 가격을 뺏을 시, 0보다 작다면 current 변수를 수정한다. (이후에 사는게 더 큰 이득이기 때문)
• 0보다 크다면 팔았을 시, 이득이 남는 구조이므로 max 변수와 크기를 비교해 갱신한다. (최대의 이익을 구해야 하기 때문)
• max는 기본으로 0으로 초기화한다. (이익을 없을 때 0을 반환하기 위함)

 

☺️ 시간복잡도

O(prices.length) 이며, O(100000) 이므로 충분하다.

 

😊 공간복잡도

정수형 변수들만 선언했기 때문에 O(1) 이다.

 

🙂 정답

class Solution {
    public int maxProfit(int[] prices) {
        int current = prices[0];
        int max = 0;
        for(int price : prices) {
            int money = price - current;
            if(money <= 0) {
                current = price;
            } else {
                max = Math.max(max, money);
            }
        }
        return max;
    }
}

 

😗 개선사항

• 별다른 조건 없이 prices 를 순회하면서 매번 min 연산을 통해 가장 싼 가격을 체크하고, 현재 가격과 가장 저렴한 가격을 뺀 가장 큰 이익을 매번 갱신하는 로직으로도 작성할 수 있다는 점을 확인했다.
• 성능상 큰 이슈는 없지만, 코드 가독성이 훨씬 좋다고 생각된다.

class Solution {
    public int maxProfit(int[] prices) {
        int min_price = prices[0];
        int maxprof = 0;

        for(int i=0;i<prices.length;i++){
            maxprof = Math.max(maxprof,prices[i]-min_price);
            min_price = Math.min(prices[i],min_price);
        }

        return maxprof;
    }
}