[코딩테스트] Programmers - 주식가격 (실패)

 
https://school.programmers.co.kr/learn/courses/30/lessons/42584?language=csharp

프로그래머스

 
 

풀이

[문제]
초 단위로 기록된 주식가격 배열 prices가 주어진다. 
가격이 떨어지지 않은 기간은 몇 초인지 return 하라. 
 
문제는 무슨 말인지 알겠는데, 입출력 예시가 이해가 안 간다.

[풀이]
간단한 방법은 prices[i] 뒤에 있는 숫자가 prices [i]보다 작지 않은 경우를 헤아리기. 
그 개수가 가격이 떨어지지 않은 시간이다. 
이중 for문을 사용하니, O(N^2) = 100,000 제곱 = 10,000,000,000 == 100억 = 1초 넘어간다. 
O(N^2) 풀이로 못 푼다. 

문제 유형이 스택/큐다. 스택/큐 풀이를 생각해야 한다. 
그런데 전혀 감이 안 온다. 
 
 

다른 사람 코드 

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int[] prices) 
    {
        int[] answer = new int[prices.Length];
        
        Stack<int> stack = new Stack<int>();
        
        for(int i = 0; i < prices.Length; i++)
        {
            // 가격이 내려가면 
            while(stack.Count > 0 && prices[stack.Peek()] > prices[i])
            {
                int index = stack.Pop();
                answer[index] =  i - index;
            }
            
            stack.Push(i);
        }
        
        while(stack.Count > 0)
        {
            int index = stack.Pop();
            answer[index] = (prices.Length - 1) - index;
        }
        
        return answer;
    }
}

 
스택을 활용한 풀이다. 
스택에 주식의 인덱스를 넣는다. 그러다가 주식 가격이 내려가는 순간, 스택에 있던 원소들을 꺼내면서, 꺼낸 주식의 가격이 현재 주식 가격보다 큰 경우, 가격이 떨어지지 않은 기간을 계산한다. 
 
스택에 여전히 주식 가격 인덱스가 남아 있다는 건 해당 주식은 가격이 내려가지 않았다는 것이다. 
그러니 이들은 자기들 기준으로 가격이 떨어지지 않는 기간을 계산해 주면 된다. 
 
 

배운점

난 스택을 단순히 탑처럼 쌓고, 마지막 넣은 것부터 빼내는 자료구조로만 이해하고 있었다. 
이 문제를 푸니, 스택은 단순 데이터를 넣고 빼는 자료구조가 아니라, Pop을 이용해서 이전 원소들을 비교할 수 있다는 것을 알게 된 것 같다. 

해결해야 할 문제를 한 가지로 보지 않고, 쪼개서 보는 것 또한 중요한 것 같다.
이 문제의 경우 주식 가격이 내려가는 순간의 주식의 시간을 계산하는 것, 주식 가격이 오르는 순간의 주식의 시간을 계산하는 것. 이렇게 두 가지로 문제를 나누었다.
꼭 해결해야 할 문제를 한 가지로 볼 필요는 없다. 쪼갤 수 있다면 쪼개서 문제를 해결하는 것도 좋은 방법인 것 같다.