[ leetcode 문제풀이 ] 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

(Best Time to Buy and Sell Stock 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Best Time to Buy and Sell Stock 문제 설명 >

 

Best Time to Buy and Sell Stock 문제는 다음과 같다.

You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

주어지는 배열 prices는 prices[i]가 i번째 일의 주식 가격을 의미한다. 주식을 사는 하루를 선택하고, 주식을 팔 미래의 하루를 선택해 수익을 최대화하고자 한다. 거래를 통해 얻을 수 있는 최대의 수익을 리턴하여라. 만약 어떤 수익도 얻을 수 없다면 0을 리턴하여라.

 

다음 두 가지 출력 예시가 주어졌다. 

 

주어진 제한 조건은 1 ≤ prices.length ≤ 10^5, 0 ≤ prices[i] ≤ 10^4 이다.

 

 

 

---

< Best Time to Buy and Sell Stock 문제 접근 >

 

profit을 최대화 하기 위해서 배열 prices에서 최솟값과 최댓값을 찾아 이 둘의 차이를 리턴한다는 방법을 사용하고자 한다. 다만 이 문제에서 주의할 점은, 최솟값을 새로 발견한 경우 최댓값은 이 위치에서부터 다시 찾아야 한다는 것이다. (주식을 산 날보다 먼저 파는 것은 말이 안되므로) 이 조건 하나만 유의하며 알고리즘을 작성해주면 된다. 그 결과는 아래와 같다. (Cpp 사용)

 

int maxProfit(vector<int>& prices) {
    int low = prices[0];
    int high = 0;
    int profit = 0;
    
    for(int i=1;i<prices.size(); i++){
        if(low > prices[i]){			// 최솟값 재설정 시 최댓값 리셋
            low = prices[i];
            high = 0;
        }
        high = max(high, prices[i]);
        profit = max(profit, high - low);
    }
    return profit;
}

 

prices 배열의 index를 1번씩만 훑는 O(n) 복잡도의 코드가 완성되었다.