Programmers - 주식가격 (C#)

📝 문제 설명

아래는 프로그래머스에서 제공한 문제 설명입니다.

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

---

❌ 제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

---

💻 완전 탐색 (C#)

using System;

public class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.Length];
        
        for(int i = 0; i < prices.Length; i++)
        {
            bool isDrop = false;
            
            for(int j = i + 1; j < prices.Length; j++)
            {
                if(prices[i] > prices[j])
                {
                    answer[i] = j - i;
                    isDrop = true;
                    break;
                }
            }
            
            if(!isDrop)
                answer[i] = prices.Length - (i + 1);
        }
        return answer;
    }
}

💻 Stack 활용 (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int[] prices) {
        int length = prices.Length;
        int[] answer = new int[length];
        Stack<int> stack = new Stack<int>();
        
        for(int i = 0; i < length; i++)
        {
            while(stack.Count > 0 && prices[i] < prices[stack.Peek()])
            {
                int idx = stack.Pop();
                answer[idx] = i - idx;
            }
            
            stack.Push(i);
        }
        
        while(stack.Count > 0)
        {
            int idx = stack.Pop();
            answer[idx] = length - (idx + 1);
        }
        
        return answer;
    }
}

완전 탐색의 경우 시간 복잡도가 최악의 경우 O(n^2) 으로 prices[]의 크기가 너무 큰 입력값이 들어오면 시간 초과가 발생할 수 있다.

하지만 Stack을 활용한 경우 시간 복잡도는 O(N)으로 효율성이 훨씬 좋다.