🏷️121. Best Time to Buy and Sell Stock
1. 문제 설명
-
주어진 배열 prices는 prices[i]가 i번째 날 주식의 가격이다.
-
주식을 한 주 사는 날과 미래의 어떤 다른 날에 주식을 팔아 최대 이익을 극대화하려고 한다.
-
이 거래로 얻을 수 있는 최대 이익을 반환하라. 이익을 얻을 수 없는 경우 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 <= 10^5
- 0 <= prices[i] <= 10^4
2. 접근 방식
방법 1) 실패
- 이중 반복문 루프롤 순회하며 앞 숫자와 뒷숫자 모두 비교하는 그리디 방식으로 가장 차이가 많이 나는 수를 찾으려고 하였습니다. 기본 TestCase에서는 원하는 결과값이 도출되어 통과를 하였습니다.
- 실패 원인 :
Time Limit Exceeded시간 초과에러로 큰 배열을 받을 경우 문제가 되어 실패했습니다.1 <= prices.length <= 10^5을 잘 체크했어야 했는데 아쉽습니다..
class Solution {
public int maxProfit(int[] prices) {
int max = 0;
for(int i = 0; i < prices.length - 1; i++){
for(int j = i+1; j < prices.length; j++){
int num = prices[j] - prices[i];
if(num > max)
max = num;
}
}
return max;
}
}
방법 2) 성공
방법 1)에서 시간초과 에러 해결을 위해 시간 복잡도를 O(n)으로 해결하기 위해 생각을 해봤습니다.- 시간 복잡도를 O(n)로 해결하기 위해
min값을prices[]배열의 첫번째 index값을 저장하고 단순 반복문을 통해min값과 비교하며 더 작은 값을 찾으면min에 저장하고, 큰수가 나왔을 경우profit을 계산하여 저장합니다. profit을 계산하여 저장할 때 기본profit의 값보다 크면 저장하도록 조건을 붙여줍니다.- 그렇게 하면 시간 초과 에러 없이 통과할 수 있습니다.
3. 구현 코드
class Solution {
public int maxProfit(int[] prices) {
int min = prices[0];
int profit = 0;
for(int i = 1; i < prices.length; i++){
if(min > prices[i]){
min = prices[i];
continue;
}
else
profit = (prices[i] - min) > profit ? (prices[i] - min) : profit;
}
return profit;
}
}- 시간 복잡도: O(n)
- 공간 복잡도: O(1)
4. 개선 사항
class Solution {
public int maxProfit(int[] prices) {
int min = prices[0];
int profit = 0;
for(int i = 1; i < prices.length; i++){
if(min > prices[i])
min = prices[i];
else
profit = Math.max((prices[i] - min), profit);
}
return profit;
}
}- 어떻게 조금 더 개선할 수 있을까 생각을 해보다 구현 코드의 else문에서
profit = (prices[i] - min) > profit ? (prices[i] - min) : profit;을 추가 조건문 없이 처리하기 위해 삼항연산자를 사용하였습니다. - 여기서 더 간결하게 코드를 작성한다면 개선 상항 코드와 같이 Math.max()를 사용하여
profit = Math.max((prices[i] - min), profit);로 수정하였습니다. - 조금 더 가독성이 좋고 간견한 코드여서 만족합니다.
5. 최종 회고
- 기본 알고리즘 문제에서는 그리디 방식으로 접근해도 문제를 해결할 수 있었지만 이번 문제에서는 아니였습니다. 어떻게 더 간결하고 가독성을 높이는 코드를 만들까 고민을 많이 하였습니다. 결과에는 만족하지만 결과적으로 간단한 문제이므로.. 조금 더 빨리 해결할 수 있지 않았을까 라는 아쉬움이 남았습니다.
- 다음에는 시간, 공간 복잡도도 잘 체크를 하며 접근하도록 해야겠습니다. 첫번째 시도에서 단순히 시간 복잡도만 생각했어도 시간을 단축할 수 있었습니다.
