주식가격 | 프로그래머스

문제

🎨 문제 바로가기

문제	레벨	정답률
주식가격	Lv.2	59%

My Code

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        for(int i = 0; i<prices.length-1; i++){
            int p = prices[i];
            for(int j = i; j<prices.length-1; j++){
                 answer[i]++;
                if(p > prices[j+1]){
                    break;
                }
            }
        }
        
        return answer;
    }
}

1. return 값을 저장할 배열 answer 생성
2. for문으로 prices 배열 전체를 돌되, 마지막 값은 어차피 0이기 때문에 i 범위에서 마지막 값은 제한하였음
   현재 prices 배열 값을 p라는 변수에 저장
3. 이중 for문으로 내부에서 i부터 prices.length-1까지 돌면서 기본적으로 ++시켜주고, p가 다음 배열 값보다 크면 반복문 stop
   ㄴ 기본적으로 ++하는 이유는 바로 다음 차례에 값이 떨어져도 1초 유지한 것이기 때문..!

최적화 코드

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            // 스택이 비어있지 않고 현재 가격이 스택의 상단 가격보다 낮으면
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                int index = stack.pop();
                answer[index] = i - index;
            }
            stack.push(i);
        }
        
        // 남아있는 인덱스에 대해 처리
        while (!stack.isEmpty()) {
            int index = stack.pop();
            answer[index] = n - index - 1;
        }
        
        return answer;
    }
}

기존 코드는 O(n^2)의 복잡도를 가지고 있었는데, 최적화시킨 코드는 O(n)의 시간 복잡도를 가진다.
=> 스택 사용했기 때문!

복잡도는 개선되었는데 코드를 짜는 입장에서는 이번 문제의 경우엔 배열을 사용하는게 더 쉬운 것 같긴 하다.
특히 answer 배열에 저장할 값을 계산하는게 바로 생각해내긴 어려운 것 같다.

answer[index] = i - index;
answer[index] = n - index - 1;

개인적으로는 효율적인 코드도 중요하지만 가독성, 혹은 코드를 읽으면서 쉽게 이해가 되는 것도 중요하다고 생각해서 두 개의 코드 중에 본인이 중요하게 생각하는 가치에 따라 선택 사용하면 될 것 같다.