문제 요약
자세한 내용은 leetcode에서 확인
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
prices[i]가 i 날의 주식 가격일 때 가장 큰 차익을 얼마나 남길 수 있는가.
input: prices = [7, 1, 5, 3, 6, 4]
output: 5
2번째 날에 1에 사서 5번째 날에 6에 팔면 5의 차익이 남는다
풀이
prices를 그래프로 머리에 그려본다. 가장 큰 차익을 남기기 위해선 가장 낮은 가격에 사서 그 이후에 가장 높은 가격에 팔아야 한다.
가장 낮은 가격 변수 minPrice와 최대 차익 변수 maxProfit를 만든다.
for loop을 돌면서 prices[i]가 현재 minPrice보다 낮으면 prices[i]가 minPrice가 된다. 다음 현재의 가격에 minPrice를 빼서 차익을 계산하고 maxProfit과 비교해서 더 높으면 그게 maxProfit이 된다.
public int maxProfit(int[] prices) {
// 제일 쌀 때 가격
int minPrice = Integer.MAX_VALUE;
// 가장 큰 차익
int maxProfit = 0;
// for loop을 한번만 돌면서 계산을 끝낼 수 있다.
for (int i=0; i<prices.length; i++) {
// 현재 가격과 비교해서 더 낮은걸 선택
minPrice = Math.min(minPrice, prices[i]);
// 현재 차익과 비교해서 더 높은걸 선택
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
return maxProfit;
}
Complexity
time: O(n) - n 노드 갯수 만큼 for loop을 돈다.
space: O(1) - 몇개 안되는 변수를 생성하였다.