LeetCode 121 Best Time to Buy and Sell Stock

nayu1105·2023년 8월 24일

leetcode 알고리즘

LeetCode

목록 보기

7/28

LeetCode 121 Best Time to Buy and Sell Stock 풀러가기

문제

prices라는 int 배열이 주어진다.

각 배열은 날짜를 의미하고, 물건을 사는 날짜, 파는 날짜 하나를 골랐을 때 최고의 이익을 계산하여 리턴한다.

예를 들어, [7, 1, 5, 3, 6, 4]라는 배열이 주어졌을 때

1 에 물건을 사고, 6에 물건을 팔 때가 이익 5로 가장 큰 이익이다.

7 일에 물건을 산다면 이익을 보는 날은 없다.

문제 분석

첫번째 시도

처음에는 이중 포문을 돌리며 두 날짜를 골라서 이익을 고르는 방법을 생각했다.

시간복잡도가 O(N^2)이지만, 다른 방법이 쉽게 떠오르지 않아 일단 코드를 짰다.

코드

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for(int i=0; i<prices.length; i++){        
        	// i번째날 이후의 날짜만 고려하기
            for(int j=i+1; j<prices.length; j++){
                if(max < prices[j]-prices[i])max = prices[j]-prices[i];
            }
        }
        return max;
    }
}

결과 : 시간초과

역시나 시간초과가 났다.

두번째 시도

고민을 하던 중에 결국 최고의 이익은 자신보다 이전날짜 중에 최솟값과의 비교 하면 된다는 심플한 방법이 생각났다.

그러면 이전 날짜의 최솟값(min)만 계속 계산해두면 시간 복잡도 O(N)만에 풀 수 있었다.

코드

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

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

       return max;
    }
}