[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee / JAVA

>> 문제설명

leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

Best Time to Buy and Sell Stock with Transaction Fee - LeetCode

 

> 1차원 배열로 주어진 변동하는 주식 가격을 받아 가장 쌀 때 사고, 가장 비쌀때 파는 문제다.

> 주식을 사거나 팔때 수수료가 발생한다.

 

> IDEA1

문제에서는 현재 상태를 주식을 판 상태(주식을 살 수 있는 상태)와 주식을 산 상태(주식을 사서 들고 있는 상태) 두가지로 분류 할 수 있다.

현재 상태가 가질 수 있는 가장 큰 이익을 저장하며 마지막 상태에서 가질 수 있는 가장 큰 이익값을 반환한다. (동적 계획법)

 

> Solution

 

class Solution {
    public int maxProfit(int[] prices, int fee) {
        // Set initial state.
        int sellState = 0;
        int buyState = -prices[0];

        for(int idx = 1; idx < prices.length; idx++){
            sellState = Math.max(
                    sellState // 판 상태 -> 판 상태
                    , prices[idx]-fee+buyState// 산 상태 -> 판 상태
            );
            buyState = Math.max(
                    sellState - prices[idx]// 판 상태 -> 산 상태
                    , buyState // 산 상태 -> 산 상태
            );
        }
        return Math.max(buyState, sellState);
    }
}

 

 

 

> IDEA2

주식 가격으로 생각한다면, 저점에서 사서 고점에 파는걸 반복하면 가장 많은 이득을 가지게 된다.

 

IDEA

 

두개의 변수를 관리한다.

하나는 저점에서 산 주식을 현재 가격에 팔았을때 최대로 가지는 수익.

하나는 전고점 대비 하한가, 즉 매수타이밍의 가격.

두개의 변수를 관리하여 문제를 해결 할 수도 있다.