주식가격

문제정의

---

자신의 주가가 언제 적자가 나는지 계산하는 문제이다. 예를 들면 문제에서 가격이 4일 때 주식을 사면 4초동안 주가가 떨어지지 않으므로 4이다. 필자는 처음에 문제를 잘못 이해하여 하나 빼고 다 틀렸다. 질문하기를 보니 다른 사람도 똑같이 그런 것 같았다. 지문의 개선이 필요해보인다.

문제풀이

---

전체 코드는 다음과 같다.

import java.util.*;

public class StockPrice {

    //프로그래머스 문제풀이 level2 주식가격

    public static void main(String[] args)
    {
        int[] prices = {1, 2, 3, 2, 3};

        int[] answer = new int[prices.length];
        int n = prices.length;
        for(int i = 0; i < n-1; i++)
        {
            for(int j = i+1; j < n; j++)
            {
                if(prices[i] > prices[j])
                {
                    answer[i] = j-i;
                    break;
                }
            }
            if(answer[i] == 0)
                answer[i] = prices.length-(i+1);
        }
    }
    
}

스택과 큐를 활용하라는 문제라고 나와있긴 하지만, 필자는 활용하진 않았다. 최대 길이가 만개이기 때문에 \(n^2\)의 시간복잡도도 충분히 돌아갈거라 생각했기 때문이다. 코드는 간단하다. 각 주식 가격에서 처음으로 주가가 떨어지는 포인트를 발견하면, 그 두 값의 차를 기록하는 것이다. 만약 if문을 거치치 않았다면 끝까지 주가가 떨어지지 않는다는 것이므로 전체에서 인덱스+1을 빼준다.

이 문제의 시간복잡도는 \(O(n^2)\)이다.

테스트

이걸 스택 큐로 분류해 놓은 이유를 잘 모르겠다. 스택/큐를 이용하면 더 빠른 시간안에 풀 수 있는것일까?