자바 알고리즘

[leetcode - Java] 121. Best Time to Buy and Sell Stock

Big Iron 2023. 8. 25. 01:23

1. 문제


  • 배열에서 뒷 요소와 앞 요소를 뺐을 때 가장 차이가 큰 값을 구하여라 image

2. 시도


배열에서 min과 max를 각각 구해 max-min을 하면 될 것 같았다. 주의할 부분으로는 max가 min보다 앞에 있을 수 있기에 인덱스 위치 파악을 해야할 듯하다.

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

        for (int i=0; i< prices.length; i++) {
            if (min > prices[i]) {
                min = prices[i];
                index = i;
            }
        }
        System.out.println("min = " + min);
        System.out.println("index = " + index);
        for (int i=index; i<prices.length; i++) {
            if (max < prices[i]) {
                max = prices[i];
            }                
        }
        System.out.println("max = " + max);

        return max-min;
    }
}

image

image

일부 테스트 케이스를 통과하며 방향은 맞아 보였다. 그러나 무작정 최솟값만 찾다 보니 큰 수가 앞에 있고 작은 수가 맨 뒤에 있는 경우는 에러였다.

3. 개선


컴퓨터로 코드를 쳐보는 것도 좋지만 가끔 생각이 안될 때 손으로 코드를 써보기도 한다. 최솟값을 찾는 것은 좋다 생각했기에 찾은 최솟값을 각 요소에서 빼보는 것을 시도해봤다.
KakaoTalk_Image_2023-08-25-13-31-36

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

        System.out.println("1 min = " + min);
        System.out.println("1 max = " + max);

        for (int i=1; i<prices.length; i++) {
            if (min > prices[i]) {
                min = prices[i];
                System.out.println("2 min = " + min);
            } else if (prices[i] - min > max) {
                System.out.println("prices[i] = " + prices[i]);
                System.out.println("3 min = " + min);
                max = prices[i] - min;
                System.out.println("2 max = " + prices[i] + " - " + min + " = " +  max);
            }
            System.out.println("4 min = " + min);
        }
        System.out.println("3 max = " + max);
        return max;
    }
}
image