.leetcode(309. Best Time to Buy and Sell Stock with Cooldown)

문제

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

문제 풀기 전

1. recursion으로 비교를 수행한다.
2. recursion식은 리턴: profit 비교: profit으로 한다.

직접 푼 풀이

소요시간: 50분(08:00 ~ 08:50)

못풀었다. 재도전하기!

느낀점

1. 위의 recursion으로는 풀지 못했다. 정확히는 풀었는데 속도 제한에 걸렸다. 실제로 모든 테스트에 통과하였으나 시간초과로 안된다고 결과가 나왔다.
2. 이 문제를 접근할때 이렇게 했으면 더 좋았을거 같다. 일단 자료형을 파악하는 것이다. 다행히 문제에 배열로 잘나와서 이 단계는 쉽다. 그 다음 배열이라면 앞에서부터 접근할지, 뒤에서 부터 접근할지를 고민한다. 그 다음 dp문제로 풀어야할 것으로 생각되면 현재 요소를 가질 수 있는 상태값을 변수로 둔다. 그 다음 그 상태값별 변수에 영향주는 건 어떤 상태인지를 파악하고 식을 만들어가는 방식인 거다.
3. 풀이를 보면 그 관계를 아주 쉽게 풀었다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    private Map<String, Integer> cache = new HashMap<>();

    public int maxProfit(int[] prices) {

        int held = Integer.MIN_VALUE;
        int sold = Integer.MIN_VALUE;
        int reset = 0;

        for (int price: prices) {
            int preSold = sold;

            sold = held + price;
            held = Math.max(held, reset-price);
            reset = Math.max(reset, preSold);

        }

        return Math.max(sold, reset);
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

나중에다시한번

• 배열문제인데 앞으로 접근하기와 뒤로 접근하는 방법 둘 다 풀어보기 바란다.