[프로그래머스] Lv.2 주식 가격

알고리즘 : 스택

---

 

문제 설명

 

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

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

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

---

시간 복잡도를 신경 써야 되는 문제
pricces 배열의 길이가 10000이므로 N^2의 복잡도를 가지게 되면 안되고 N의 복잡도를 가져야 된다.
처음에는 N^2의 풀이법만 생각이 났다.

기존 풀이

1. 기준이 되는 값을 정한다

• 앞에서 부터 순차적 진행

2. 기준이 되는 값과 비교하며 작은 값이 나올 때까지 카운트 증가
3. 작은 값 만날시 카운트 값 따로 배열에 저장

이렇게 진행하면 오름차순의 경우에 N^2이 나오므로 이렇게 풀면 안된다.

그러면 우리는 불필요한 연산시간을 줄여야한다.
연산 시간을 줄이기 위한 방법으로 여기서 스택을 사용한다.

남는 시간을 확정시키기 위한 조건은 이전의 price가 현재의 price보다 클 경우이다.
예를 들어 1 3 5 4 라고 할 경우, 5는 4가 들어오는 순간 남은 시간이 1초로 확정된다.
이것을 활용하여 남는 시간이 확정된 시간들을 제외하면 불필요한 연산 시간을 감소 시킬 수있다.

---

올바른 풀이

위의 설명과 같이 남은 시간이 확정된 가격을 제외하면 연산 시간이 감소된다.
이를 위해서 들어온 배열의 인덱스 기준으로 남는 시간 배열을 만든다.

1. 남는 시간 배열 생성

• 이곳에는 1 3 5 4 면 0 1 2 3순으로 배열에 들어가는 것

2. 1 3 5 4 순서로 스택에 push

• 이때 지금 들어가는 가격이 이전 가격보다 쌀(작을) 경우 이전 가격의 남는 시간을 확정 시킨다.
• 인덱스 값의 차로 기간이 결정된다.

3. N 길이 만큼 과정을 수행 후, 스택 안에는 끝까지 유지되는 가격들만 존재하므로 최종 시간 계산

• (N-1) - 해당 인덱스 = 남은 시간

확정시키는 과정

2번 과정

3번 과정

---

코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int N = prices.length;
        // 남는 시간 배열 선언 및 초기화
        int[] answer = new int[N];
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < N; i++){
            // 스택이 not empty, 이전 Top이 클 경우
            while ( !stack.isEmpty() && prices[stack.peek()] > prices[i] ){
                int targetIdx = stack.pop();
                answer[targetIdx] = i - targetIdx;   
            }
            stack.push(i);
        }

        // 최종 스택에서 남은 시간 확정 
        for (int i : stack){
            answer[i] = N - 1 - i;
        }

        return answer;

    }
}