날짜별 주식가격이 주어지고 주식가격을 특정일에 사서 특정일에 판다고 가정했을때
가장 큰 수익을 냈을경우 그 수익을 구하는 문제입니다.
수익을 내지 못할경우 0을 반환합니다.
문제 접근
단순 반복을 해서 구하면 될거라고 생각했습니다.
2중 반복문을 통해 날짜A를 기준으로 A의 다음날짜들을 탐색하는 방법입니다.
public int maxProfit(int[] prices) {
int ret = 0;
for (int i = 0; i < prices.length-1; i++) {
for (int j = i+1; j < prices.length; j++) {
if (prices[i] > prices[j]) {
break;
} else {
ret = Math.max(ret, prices[j] - prices[i]);
}
}
}
return ret;
}
시간복잡도
당연히 시간초과가 났습니다.
그 이유는 prices의 길이가 10의 5승이기 때문입니다.
O(n2)의 시간복잡도를 갖고있는 제 코드는 효율성면에서 많이 부족합니다.
다른사람의 풀이
시간복잡도를 O(n)으로 줄인 코드입니다.
최소값을 기억할 변수를 선언하여 탐색할때마다 최소값을 저장합니다.
저장된 최소값과 지금 바라보는 요소의 차를 구해서 Math.max함수를 사용해 ret변수에 담아줍니다.
위 과정을 매번탐색동안 거쳐 최대수익을 구할 수 있습니다.
public int maxProfit(int[] prices) {
int ret = 0;
int min = (int) 1e9;
for (int i = 0; i < prices.length; i++) {
min = Math.min(min, prices[i]);
ret = Math.max(ret, prices[i] - min);
}
return ret;
}
느낀점
문제풀이법이 떠오르지 않을때에는 그림으로 그래프를 그려가며 이해하면 수월하게 풀리는것 같습니다.
문제를 이해하기위해 적극적으로 노력해야겠습니다.
참고
도서 : 파이썬 알고리즘 인터뷰
'LeetCode' 카테고리의 다른 글
[LeetCode] 55. Jump Game (0) | 2023.08.25 |
---|---|
[LeetCode] 122. Best Time to Buy and Sell Stock II (0) | 2023.08.25 |
[LeetCode] 189. Rotate Array (0) | 2023.08.25 |
[LeetCode] 169. Majority Element (1) | 2023.08.24 |
[LeetCode] 80. Remove Duplicates from Sorted Array II (0) | 2023.08.24 |