LeetCode 121번 - Best Time to Buy and Sell Stock

문제 살펴보기

int 자료형 배열이 주어진다. 배열의 인덱스는 일차에 해당하고, 각 숫자는 해당 일차의 주식 매매가를 의미한다.

 

예를 들어 [3, 5, 9]와 같은 배열이 주어진 경우 다음과 같은 의미를 가진다.

 

인덱스 0, 숫자 3 -> 0일차, 주식 가격 3

인덱스 1, 숫자 5 -> 1일차, 주식 가격 5

인덱스 2, 숫자 9 -> 2일차, 주식 가격 9

 

주어진 배열을 바탕으로, 주식을 구매하고 다시 팔아서 수익을 남기려고 한다.

최대 얼마의 수익을 낼 수 있을까?

 

---

생각의 흐름

1. 구매하는 일자(인덱스)는 판매하는 일자(인덱스)보다 빨라야 한다.

2. 이중 반복문을 사용할 경우 계산 시간이 너무 길어져 시간 초과가 된다. 이 문제의 핵심!

 

2번 이유로 인해 이중 반복문을 사용할 수 없다.

최저값과 최대수익을 저장할 변수를 만들고, 단일 반복문을 이용해 두 값을 계속 최신화하는 방식으로 푸는 것이 좋겠다. 

 

---

풀어보기

int minPrice = prices[0], maxProfit = 0;

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