[프로그래머스] 스택/큐 주식가격 JAVA 자바풀이

<문제>

 

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

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

입출력 예

pricesreturn

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

입출력 예 설명

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

---

 

스택과 큐에 대해서는 예전부터 공부했었지만 활용을 제대로 해보지 못했던 것 같다.

 

이번 문제에서도 너무 익숙한 배열로 풀어내고 나서야 문제 종류가 스택/큐 인 것을 발견했다.

 

그래서 다시 초기화하고 풀어봤다.

 

 

처음엔 스택을 어떻게 쓰는건지 조금 헤맸는데 이해하고나니 엄청 간단했다.

 

제일 중요한것은 스택의 용도였다.

 

스택에는 아직 자기보다 작은숫자를 만나지 못한, 아직 떨어지지 않은 prices배열의 index값을 넣어둘 것이다.

 

 

<풀이>

 

조금 더 리얼하게 하기 위해 예시값을 조금 바꿔보겠다.

 

아래 price 값이 내가 0초부터 1초마다 1주씩 분할 매수한 삼성전자의 만원 단위 주식이라고 생각해보자.

 

예를들어 price의 배열이 [8, 9, 10, 9, 10] 라면

 

 

<지금은 0초>

 

먼저 0초의 시간을 stack에 넣어 기록해준다.

 

나는 0초에 주식을 샀다.

 

현재 stack 값 [0]

 

 

 

<지금은 1초>

 

그 후 1초인 현재 주식가격과 stack에 0초대에 주식을 샀던걸 확인하여

 

0초의 가격과 비교해본다.

 

즉, price[0]과 price[1]을 비교해본다.

 

다행이다 안떨어지고 올랐다.

 

0초에 샀던 주식은 1초의 시점에 아직 손해는 안봤군!

 

그럼 0초는 그대로 두고 1초도 stack에 기록해둔다.

 

현재 stack의 값 [0, 1]

 

 

<지금은 2초>

 

그럼 2초 현재의 가격과 stack에 마지막에 적혀있는 1초,

 

그때의 주식가격을 비교해본다.

 

9만원 -> 10만원

 

1초에 샀던 주식도 2초대에 올랐다.

 

두근두근 이렇게 부자가 되는것인가!!

 

stack에 2를 넣어준다

 

현재 stack의 값 [0, 1, 2]

 

 

<지금은 3초>

 

현재 주식과 stack의 마지막에 적혀있는 2초의 주식을 비교해본다

 

10 -> 9

 

2초에 10만원에 샀었는데 3초에 9만원으로 떨어졌다...

 

이럴수가!!

 

눈물을 머금고 stack에서 2초는 뺀다.

 

현재 stack의 값 [0, 1]

 

그리고 주식거래노트에 적어준다. 

 

2초에 산 주식은 1초만에 떨어졌다.....

 

이것을 answer 배열에 넣어주면

 

[0, 0, 1, 0, 0]

 

아니 그럼 그 전에 샀던 것들도 다 떨어진거 아니야??

 

불안한 마음과 함께 현재 stack의 맨 마지막에 적혀있는 1초의 가격을 확인해본다

 

1초대에도 9만원에 샀었구나. 손해는 안봤네

 

다행이다. stack을 그대로 놔둔다.

 

stack에 3초를 적어준다.

 

현재 stack [0, 1, 3]

 

 

<지금은 4초>

 

현재 4초의 가격과 stack 에 맨 마지막에 적혀있는 3초의 가격과 비교해본다.

 

9 -> 10

 

4초대에는 10만원으로 올랐다.

 

다행이다!

 

stack에 4를 넣어준다.

 

현재 stack의 값 [0, 1, 3, 4]

 

 

지금까지의 진행상황을 확인해본다.

stack [0, 1, 3, 4]

answer[0, 0, 1, 0, 0]

 

stack에는 아직 떨어지지 않은 주식거래의 초단위가 적혀있다.

그럼 4초인 현재 기준,

answer인 주식거래노트에 지금까지 각각의 거래가 얼마나 떨어지지 않고 버티고있는지 계산해서 적어준다.

 

4초에 샀던거는 방금산거니까 0초

3초에 샀던거는 4 - 3 = 1초를 버텼군

1초는 4 - 1 = 3초를 버텼군

0초에 산건 4 - 0 = 4초를 버텼군

 

2초는 아까 1초만에 떨어져서 적어놨었지

 

그럼 시간순서대로 answer 는 [4, 3, 1, 1, 0] 이렇게 버텼구나!

 

 

이런 느낌의 로직이다.

 

stack 활용해서 쉽게 설명된게 없어서 혹시나 필요한 사람들을 위해 조금 더 풀어서 적어보았다.

 

예시가 완벽하게 문제와 똑같지 않으니,

여기서는 stack이 어떤용도로 쓰이는지 정도만 이해하고 전문가들의 풀이를 보면 편할 것이다!

 

아래는 제출한 코드이다.

 

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int len = prices.length;
        int[] answer = new int[len];
        Stack<Integer> stack = new Stack<>();
        
        for(int i=0; i<len; i++){ // prices 배열의 크기동안
            
            //비교대상stack 인덱스의 price값이 현재 비교중인 인덱스의 price값보다 작다면
            while(!stack.isEmpty() && prices[i] < prices[stack.peek()]){ 
                //stack에서 해당값은 빼주고
                int idx = stack.pop();
                //answer 인덱스에 얼마만에 찾았는지 넣어준다. 
                answer[idx] = i - idx;
            }
            stack.push(i);
        }
        System.out.println(stack);
        
        while(!stack.isEmpty()){
            int leftIdx = stack.pop();
            answer[leftIdx] = len-leftIdx-1;
        }
        
        return answer;
    }
}