문제링크

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

구현방법

Stack을 이용해서 처음값은 넣어두고 스택의 넣어져있는 값중 가장 위의 값이 다음 값보다 작거나 같은 경우는 떨어지지 않았기때문에 push를 통해 넣어주다가 다음 값이 작아질 경우 stack에 들어있는 값들을 비교해가면서 stack.peek()값이 더 큰 경우를 전부 pop()을 해주면서 초를 계산해서 answer배열에 맞춰서 넣어줍니다.

그리고 마지막에 stack에 남아있는 것들을 전부 빼주면서 계산하여 각 초에 맞춰서 넣어줍니다.

---

처음에는 2중 for문을 통해서 첫 for문은 기준 값을 그 안의 for문은 비교 값을 계산해서 가격이 떨어질때 boolean을 통해서 계산했는데 이경우 prices의 길이가 만약 10만개일경우 100억초가 걸리기 때문에 시간초과가 발생했엇습니다.

구현알고리즘

Stack

CODE

스택을 이용한 솔루션

import java.util.Stack;
class Solution
{

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

        int len = prices.length-1;
        Stack<price_day> stack = new Stack<>();

        for(int index = 0;index <= len;index++) {
            //비어있으면 넣기
            if(stack.isEmpty()){
                stack.push(new price_day(prices[index],index));
                continue;
            }
            //넣어진 값의 가장 위에 있는 값이 다음 값보다 작거나 같을경우
            if(prices[index] >= stack.peek().price){
                stack.push(new price_day(prices[index],index));
            }else{
                //스택의 가장위로 올라오는 값이 prices보다 크면 계속 뽑음
                while(!stack.isEmpty() && prices[index] < stack.peek().price){
                    price_day p = stack.pop();
                    answer[p.day] = index - p.day;
                }
                stack.push(new price_day(prices[index],index));
            }
            

        }
        while(!stack.isEmpty()){
            price_day p = stack.pop();
            System.out.println(p.day);
            answer[p.day] = len - p.day;
        }
        return answer;
    }

}
class price_day{
        int price;
        //그날 날짜
        int day;
        price_day(int price, int day){
            this.price = price;
            this.day = day;
        }
    }

실패 코드(효율성 시간초과)

---

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

        //가격이 떨어질경우 true 체크
        boolean check[] = new boolean[prices.length];


        for(int index = 1;index <prices.length;index++) {
            for(int checking = 0; checking< index;checking++) {
                //아직 가격이 안떨어졌을경우
                if(!check[checking]) {
                    if(prices[checking] <= prices[index]) {
                        answer[checking]+=1;
                    }else {
                        answer[checking]+=1;
                        check[checking]= true;
                    }
                }

            }
        }





        return answer;
    }

}