[프로그래머스] 주식가격 (JAVA)

문제 출처 - Programmers

문제는 여기

코딩테스트 연습 - 주식가격

---

[풀이]

1. 스택이 비어있지 않고, 현재 가격이 스택의 peek() 가격보다 작다면 가격이 떨어졌다는 것이다.

2. 스택의 가격보다 떨어졌으니 현재 인덱스에서 스택의 peek()을 빼줘서 answer에 넣어준다.

3. 스택의 peek()을 제거해준다.

4. 1. 의 조건을 만족하지 않을 때까지 반복한다.

5. 스택에 현재 인덱스를 넣는다.

6. 모든 값들을 탐색해야 하므로 prices의 길이만큼 반복한다.

7. 스택에 남아있는 값이 있다면 가격이 떨어진 적이 없던 것이므로 전체 기간에서 스택에 남은 인덱스를 빼 answer에 넣어준다.

8. 결과를 출력한다.

[접근]

1. 문제 유형을 모르고 풀었다면 그냥 배열을 사용해서 풀었을 것 같지만 스택/큐인 것을 알고 문제를 풀어 스택을 사용해서 문제를 풀어보고자 하였다.

2. 스택에 값을 넣어주고 현재 값과 이전의 값들을 비교하면서 총개수를 구해주면 되겠다고 생각하였다.

[코드]

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> st = new Stack<>();

        // 모든 값들을 탐색
        for (int i = 0; i < prices.length; i++) {
            // 스택이 비어있지 않고, 현재 가격이 이전 가격보다 작으면
            // 과거에 들어있던 값들도 다 체크를 해줘야하므로
            // 반복문을 통해서 검사
            while (!st.isEmpty() && prices[i] < prices[st.peek()]) {
                // 현재 인덱스 - 스택의 peek의 인덱스
                answer[st.peek()] = i - st.peek();
                // 스택에서 빼기
                st.pop();
            }
            // 스택에 넣기
            st.push(i);
        }

        // 스택이 비어있지 않다면
        // 한번도 가격이 떨어지지 않은 경우라는 뜻
        // 스택이 모두 비워질 때까지 반복해서 체크
        while (!st.isEmpty()) {
            // 가격 시점의 마지막 인덱스 - 스택의 peek의 인덱스
            answer[st.peek()] = (prices.length - 1) - st.peek();
            // 스택에서 빼기
            st.pop();
        }

        return answer;
    }
}