[알고리즘] 프로그래머스 2단계 - 주식 가격

프로그래머스 문제 링크

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

 

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다.

 

예시

 

prices

[1, 2, 3, 2, 3]

 

return

[4, 3, 1, 1, 0]

 

import java.util.*;
import java.util.stream.Collectors;

public class Solution {

    public static void main(String[] args) {
        int[] solution = new Solution().solution(new int[]{1, 2, 3, 2, 3});

        for (int item : solution) {
            System.out.println(item);
        }
    }

    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];

        ArrayDeque<Time> deque = new ArrayDeque<>();
        
        // 유지되는 시간을 측정
        // 각 유지되는 시간은 바로 다음까지를 보고 1초로 한다.

        // 큐에 현재 인덱스와 주식의 값을 갖는 클래스 타입을 만들어서 큐 생성
        // 각 시간 클래스는 인덱스를 갖는다.
        // 각 시간 클래스는 자신보다 작은 값이 나오면 원시배열에 기록한 다음 큐에서 제거
        // 시간 클래스의 값과 같거나 큰경우 시간 필드의 값을 1 더한다.

        int currentIdx = 0;

        deque.add(new Time(0, prices[0], true));

        while(!deque.isEmpty()){
            // 유지 시간 증가 인지 아닌지 미리 검증 하기 위함
            Time item = deque.pop();

            // 값이 유지 되지 않으면 기록 한다.
            // 마지막 인덱스의 경우 현재 상태 기록 한다.
            if (prices[currentIdx] < item.val || currentIdx == prices.length - 1) {
                answer[item.index] = item.cnt;
            // 값이 유지 된 경우 cnt 값 증가 후 큐에 다시 넣는다.
            } else {
                item.increaseVal();
                deque.add(item);
            }

            // 큐를 한번 순회 한지 여부 체크
            // 현재 인덱스 증가
            // 큐에 현재 인덱스 클래스 추가
            if (item.isLast && currentIdx != prices.length - 1) {
                currentIdx++;

                item.uncheckLast();

                deque.add(new Time(currentIdx, prices[currentIdx], true));
            }

        }
        return answer;
    }
    class Time {

        int index;

        int val;

        int cnt;

        boolean isLast;

        public Time(int index, int val, boolean isLast) {
            this.index = index;
            this.val = val;
            this.isLast = isLast;
        }

        public void increaseVal() {
            this.cnt++;
        }

        public void checkLast() {
            this.isLast = true;
        }

        public void uncheckLast() {
            this.isLast = false;
        }
    }
}