.leetcode(121. Best Time to Buy and Sell Stock)

문제

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

Best Time to Buy and Sell Stock - LeetCode

문제 풀기 전

1. 가장 먼저 생각한건 왼쪽, 오른쪽 양쪽에서 와서 가장 작은값과 큰값의 차이를 구하는 것이었다. 그럴싸해보이지만 이걸로 20분 해맸다.
2. 그러다 위 방법이 복잡해지자 이런 복잡한건 알고리즘이 아니다라는 생각에 왼쪽부터 차근히 가고 값이 작아지면 작은 값을 업데이트, 커지면 그 차이를 비교해서 diff 업데이트를 하면 되겠다는 생각이 들었다.

직접 푼 풀이

소요시간: 26분(08:08 ~ 08:34)

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

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

        return maxdiff;
    }
}

느낀점

1. 일단 간단하게 생각해야한다. 복잡해도 간단하게 잘라서 생각했어야 했다. 왼쪽, 오른쪽 인덱스를 움직이는 생각을 하다보니 문제가 복잡해지고 코드도 복잡해져서 미로에 빠졌다.
2. 애초에 왼쪽부터만 생각했다면 5분안에 답을 냈을지도 모른다.
3. 솔루션도 위와 같이 해결했다.

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

1. 제한값이 있는지 확인한다.

2. 최대 시간복잡도나 최대 경우의 수를 유추해본다.

3. 기본으로 주어지는 메소드에서 해결이 가능한지 생각해본다. > 메소드를 만들어 사용한다. > 전역변수를 과감히 도입한다.

4. recursion(Brute Force, Back Tracking)으로 가능할지 먼저 생각해본다. 이 후에 iterative하게 풀 수 있을지도 생각해본다. iteratvie하게 풀때는 stack을 이용해본다. 경우의 따라 queue를 사용해볼 수 있다.

5. recursion일 경우, 종료조건을 먼저 만들고 로직을 만든다.

6. 주어진 Input데이터를 더렵힐 수도 있다고 생각해본다. 덮어쓰기한다던지, 더해서 합값으로 치환한다던지 말이다.

7. TreeNode는 left,right,val으로 구성해볼 수 있고 ListNode는 val,next로 구성해볼 수 있다.

8. ListNode문제가 나오면 꼭 그림으로 next관계를 이해해보자. 그리고 기존의 데이터를 이용해서 이어잘라붙이기에 대한 시도도 꼭 해보자.

9. 배열에서 갯수를 센다고 하면 Brute force, HashMap, Sorting방법을 생각해보자.

10. 만약에 대다수를 구하는 문제라면 Boyer–Moore majority vote algorithm를 생각해보자.

11. Arrays 디버깅할때 Arrays.stream(nums).boxed().forEach(System.out::println);하면 결과를 볼수 있다.

12. 순서, 부호를 이용해서 공간을 절약할 수 있는지 생각해본다.

13. 간단한것 부터 생각해본다. 배열이 있다면 인덱스를 양방향으로 사용하기보다는 한방향으로 사용해보고 정안되면 양방향으로 생각을 바꿔보자. 간단하게 생각하고 간단하게 문제를 만들줄 알아야한다.