Leet Code - 121. Best Time to Buy and Sell Stock(C++)

포타토·2020년 2월 13일

알고리즘

목록 보기

47/76

예제: Best Time to Buy and Sell Stock

문제
Say you have an array for which the i'th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

풀이

가장 작은 수와 가장 큰 수의 차이를 구하는 문제인데, 가장 작은 수의 인덱스가 가장 큰 수의 인덱스보다 앞에 있어야 한다.

처음에 풀었던 방법은, 아주 쉽게 2중 for문을 돌면서 값을 계산하는 것이다. 당연히 쉽게 풀 수 있었지만, 소요시간이 엄청났다. 시험이었다면 효율성에서 단박에 탈랐했을 시간이다.

그래서 두 번째는 하나의 for문을 돌며, 가장 작은값을 발견한다면 그 값은 minNum으로 지정한다. 그 후로 발견되는 값들이 minNum보다 크다면, minNum과의 차를 구해서 이전에 구해놓았던 답보다 크다면 이를 갱신해준다.

전체적인 소스코드는 아래와 같다.

소스 코드

/* CASE1 */
class Solution {
public:
	int maxProfit(vector<int>& prices) {
		int size = prices.size();
		int res = 0;

		for (int i = 0; i < size - 1; i++) {
			for (int j = i + 1; j < size; j++) {
				res = max(res, prices[j] - prices[i]);
			}
		}

		return res;
	}
};


/* CASE2 */
class Solution {
public:
	int maxProfit(vector<int>& prices) {
		int res = 0;
		int size = prices.size();
		if (!size) return res;

		int minNum = prices[0];
		for (int i = 1; i < size; i++) {
			if (prices[i] < minNum) {
				minNum = prices[i];
			}
			else if (prices[i] > minNum) {
				res = max(res, prices[i] - minNum);
			}
		}

		return res;
	}
};