문제
배열에서 주식을 구매하고, 팔았을 때 언제 가장 큰 수익을 낼 수 있는가? 에 대한 문제
문제 확인하기
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.
Example 1:
Input: prices = [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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 105
0 <= prices[i] <= 104
풀이
처음에 일단 바로 풀고, 반례에 대해 커버하는 코드를 추가하려고 했음. 그런데 의외로 반례가 없어서 당황
포인트는, 현재 내가 위치한 시점에서, 내 앞의 원소들 중 "가장 작은 값"과 나를 비교하는 것이다.
주식을 팔 수 있는 상황이라면 (앞에 나보다 작은 값이 있었다면), 그 값과 현재까지의 최대 이익을 비교해서 업데이트한다.
처음에는 minIdx, maxIdx를 써야하나도 고민했으나, 필요없는게 어차피 내 앞의 값 중 가장 작은 값과 계산했을때의 값이 기존의 최댓값보다 작으면 skip하면 되기 때문에 별도의 idx는 필요하지 않다.
이미 앞에서 더 큰 값이 나왔다면 그걸 쓰면 되기 때문이다.
ex) 7,2,3,1,5
idx: 0일때, min = max = prices[0]으로 해두고 시작
idx: 1일때, 현재 min(7)보다 내가(prices[1]=2) 작으므로 주식을 팔 수 없다. min을 2로 update
idx: 2일때, 현재 min(2)보다 내가(prices[2]=3) 크므로 주식을 팔 수 있다. calMax(현재까지의 최대 이익)를 1로 update
idx: 3일때, 현재 min(2)보다 내가(prices[3]=1) 작으므로 주식을 팔 수 없다. min을 1로 update
idx: 4일때, 현재 min(1)보다 내가(prices[4]=5) 작으므로 주식을 팔 수 있다. calMax(1)와 현재 이익(4)를 비교해서 calMax를 4로 update
public static int maxProfit(int[] prices) {
int min = prices[0], max = prices[0], calMax = 0;
boolean flag = false;
for (int i = 1; i < prices.length; i++) {
if (min > prices[i]) {
min = prices[i];
flag = false;
} else if (min < prices[i]) {
if (!flag || max < prices[i]) {
max = prices[i];
if (max - min > calMax) {
calMax = max - min;
}
flag = true;
}
}
}
return calMax;
}
총평
어려울 줄 알았으나 생각보다 쉬웠음
재밌는 문제였다!
댓글