리트코드 - 121. Best Time to Buy and Sell Stock

리트코드 - 121. Best Time to Buy and Sell Stock

출처 - https://leetcode.com/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 배열 prices[i]는 각 날짜별 주식의 가격을 나타냅니다.

당신은 한 주식을 구입하는 날짜와 그 주식을 미래의 어떤 날에 판매하는 날짜를 선택하여 이윤을 극대화하려고 합니다.

이 거래로 얻을 수 있는 최대 이윤을 반환하세요. 만약 어떠한 이윤도 얻을 수 없다면 0을 반환하세요.

 

의사코드

최대값을 0으로 저장 최소값을 배열이 가질수 있는 최대값보다 큰 수로 지정 반복문 시작[nums 배열]     만약 배열값이 최소값보다 작다면         최소값에 배열 값 저장     아닌 경우         만약 배열값에서 최소값 뺸 값이 최대값보다 크다면             최대값에 이 값을 저장 반복문 종료 최대값 리턴

풀이코드

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int min = 10000 + 1;

        for (int i = 0; i < prices.length; i++) {
            if (min > prices[i]) {
                min = prices[i];
            } else {
                if (max < prices[i] - min) {
                    max = prices[i] - min;
                }
            }
        }
        
        return max;
    }
}

코드설명

최대값에는 0을 최소값에는 배열에 들어갈수 있는 수보다 큰 수를 넣는다.

이후 배열을 순회하면서 최소값보다 작은 값을 발견하면 저장하고, 만약 작은 값이 아니라면 배열요소에서 최소값을 빼본다.

이 뺀 값이 최대값보다 크다면 최대값에 값을 저장한다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

문제를 풀며 생각한 흐름과 배운 점

처음에는 for문을 두 번 사용하면서 배열을 각각 순회했는데 시간 초과 오류가 떴다.

문제에서 최대의 이익이라고 했으니까 배열과 별도로 구분하여 이 값을 관리하면 생각보다 쉽게 구할 수 있겠다는 생각을 했다.

 

다른코드

class Solution {
    public int maxProfit(int[] prices) {
        int lsf = Integer.MAX_VALUE;
        int op = 0;
        int pist = 0;
        
        for(int i = 0; i < prices.length; i++){
            if(prices[i] < lsf){
                lsf = prices[i];
            }
            pist = prices[i] - lsf;
            if(op < pist){
                op = pist;
            }
        }
        return op;
    }
}

리트코드에서 다른 사람의 코드를 보니 나의 생각과 비슷하게 풀었던 걸 볼 수 있다.

한가지 배운점은 최소값에 큰 값을 대입할때 Integer.MAX_VALUE 라는 상수를 이용해 대입했다는 것이다.

내 코드처럼 직접 값을 입력하는 것보다 저렇게 입력하니 조금 더 직관적인 것 같다.

 

정리

의사코드로 먼저 짠 코드로 해결이 안되면, 다시 싹 의사코드를 지우고 다른 방법을 생각해보자.