리트코드 - 122. Best Time to Buy and Sell Stock II

리트코드 - 122. Best Time to Buy and Sell Stock II

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

 

문제 설명

주어진 정수 배열 prices[i]는 각 날짜별로 주식의 가격을 나타냅니다.

매일마다 주식을 사고 팔 수 있습니다. 언제든지 최대 한 주식만 보유할 수 있습니다. 그러나 주식을 사면 즉시 같은 날에 팔 수 있습니다.

최대 이윤을 찾아 반환하세요.

의사코드

최소값을 매우 큰수로 지정 최대값을 0으로 지정 반복문 시작[prices 배열의 마지막 전까지 순회]     만약 최소값(매우 큰수)보다 값이 작으면         최소값에 배열 값을 저장     만약 배열 다음값이 현재 배열값보다 작으면         최대값에 (배열-최소값) 더한다         최소값에 다시 현재 배열값 저장 반복문 종료 만약 배열의 마지막 값이 최소값보다 크다면     최대값에 마지막값-최소값 더한다 최대값 리턴

풀이코드

class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE;
        int max = 0;

        for (int i = 0; i < prices.length - 1; i++) {
            if (min > prices[i]) {
                min = prices[i];
            } 
            if (prices[i + 1] < prices[i]) {
                max += prices[i] - min;
                min = prices[i];
            }
        }

        if (prices[prices.length - 1] > min) {
            max += prices[prices.length - 1] - min;
        }

        return max;
    }
}

코드설명

주가가 변동 될 때 사고 팔고를 매일 하여 최대의 이익을 실현하는 방법이다.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

예제 코드들을 보면 단순히 차액이 큰 것 뿐만 아니라 차액들의 합이 최대가 되어야 한다.

낮은 가격일 때 저장하여 가격이 떨어지기 전날 팔면 최대의 이익이 된다.

 

예시코드 1번을 예를 들어 보자

배열 {7,1,5,3,6,4}에서 첫째 날 7이 가장 낮은 가격이므로 저장한다.

하지만 다음 날 가격이 1로 떨어졌으므로 다시 가장 낮은 가격인 1을 저장한다.

가격이 6이 되는 날 팔면 6-1=5의 이익을 보지만 이는 더 이익 볼 수가 없다.

 

바로바로 파는 것이 중요하다.

가격이 5가 되는 다음날 3이 되므로, 5가 되는날 팔아버려서 이익을 5-1=4 실현하고, 다시 5를 가장 낮은 가격으로 저장한다.

그리고 또 다음날 3이 되었으므로 그 값을 가장 낮은 가격으로 저장하고 가격이 6에서 4로 떨어진걸 보고 6에서 팔아버린다.

6-3=3 의 이익이 실현되었다.

 

토탈 이익은 3+4 = 7 의 이익이다.

 

코드에서 for문을 순회하는데 인덱스 오류가 나기 때문에 배열의 마지막은 따로 처리를 해주었다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

문제를 풀며 생각한 흐름과 배운 점

문제를 어찌저찌 풀었지만 뭔가 찝찝한 느낌은 지울수가 없었다.

그 이유의 첫번째는 왜 가격이 떨어졌을때 즉각즉각 파는게 가장 큰 이익인지 궁금해서이고,

두번째는 내 코드를 더 줄이는 방법은 없을까여서였다.

 

다른 코드

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

        for (int price : prices) {
            if (price > stockOnHand) {
                profit += (price - stockOnHand);
            }
            stockOnHand = price;            
        }
        return profit;
    }

역시나 다른 사람의 코드를 보니 더 줄이는 방법은 있었다.

다만 이 부분은 다시 한 번 공부가 필요해서 다시 업데이트 할 예정이다..

 

정리

조금 더 공부 후 업데이트 예정