[JAVA] 프로그래머스 LEVEL2: 주식가격

 

프로그래머스

 

문제 설명

 

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

제한 사항

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

입출력 예

prices                                                                                               return

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

---

프로그래머스에 종종 테스트케이스랑 설명이 빈약한 게 있는데 이문제가 딱 그랬다..

중요한 건 3초에서의 시점! 3->2->3의 양상을 띄우는데 여기서 봐야 할 건 3->2에서 떨어질 때의 1초이다 다시 3으로 오르는 건 무시한다..

이문제가 stack인 이유가있었다 count 변수를 생성해 조건일 때 증가시켜 주면 이문제에서는 답이 다르게 출력된다

조건에 맞게 stack에 넣어준 후 조건이 아닐 때 그 stack의 size를 보면 결괏값의 초가 나오기 때문이다!

내가 만든 다른 테스트케이스로 문제를 풀어보자

1초에서 주가가 상승하다가 1에서 주가가 하락한다 이걸 2초라 치는 거다 이문제에선.. 그 뒤는 볼 필요가 없다는 점

이걸 토대로 코드로 옮겨봤다

---

import java.util.ArrayDeque;

public class PRO_CT_17 {
    public static int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        ArrayDeque<Integer> deque = new ArrayDeque<Integer>();

        for(int i=0;i<prices.length;i++){
            for(int j=i+1;j<prices.length;j++){
                deque.addLast(prices[j]); //데큐에 add해주고
                if(prices[i]>prices[j]) { //만약 넣은 값이 나보다 작다면
                    break; //break해주고
                }
            }
            answer[i]=deque.size(); //지금까지의 데큐 사이즈를 결과값에 삽입
            deque.clear(); //다음 연산을 위해 clear
            if(i==prices.length-1) answer[i]=0; //마지막은 무조건 0 이 들어가야하기때문에 0 삽입
        }

        return answer;
    }

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

    }
}

이번에도 deque를 사용해 stack을 구현하여서 풀었다!

이 문제 또한 prices의 길이가 100,000이라서 O(N²)으로 풀지 않으려고 노력했다!

정확성, 효율성 모두 통과!!