[프로그래머스] 주식가격 - java

문제 설명 :

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

프로그래머스

 

문제 요약 :

1. 각각의 시간 단위에 대해, 현재 기준 주식가격이 하락하지 않는 기간 구하기

 

쉽게 말해서,

[1, 2, 3, 2, 3]이라는 예가 있다.

1초 시점에는 1원의 가치,

2초 시점에는 2원의 가치,

3초 시점에는 3원의 가치,

4초 시점에는 2원의 가치,

5초 시점에는 3원의 가치를 나타내는 배열이다.

 

1초 시점에는 1원이기에, 5초 시점까지 주식의 가치가 더 떨어지는 시점이 없다.

따라서 1초 시점은 4초간 가격 하락이 없다.

 

3초 시점에서는 3원이기에, 4초 시점까지 주식의 가치가 더 떨어지는 시점이 없다.

4초에는 2원으로 1원의 가치가 하락하기에, 1초간 가격 하락이 없다.

 

이를 각각의 시간 단위에 따라 배열로 나타내면 다음과 같다.

[4, 3, 1, 1, 0]

 

문제 풀이 시간 : 20분

문제 성공 여부 : 성공

 

 

접근 방법(성공) :

1. 스택을 활용
2. 1초 시점부터 n초까지 가격이 증가할 경우 스택에 계속 push
3. 스택의 top에는 항상 1초~n 초까지 중 가장 큰 가격이 저장된다.
4. 만약 스택의 top 보다 주식가격이 작을 경우, 해당 가격보다 큰 가격들은 모두 pop을 하여 시간을 측정한다.

다음과 같은 예시가 있다.

[1, 2, 3, 4, 5, 6, 3] 

 

1~6까지는 가격의 하락이 없으니 계속해서 스택에 가격과 인덱스를 삽입해 준다.

 

그럼 스택의 top은 price인 6과 index인 5가 저장된다. (6,5) 

 

다음 가격인 3은 6보다 작은 수이기 때문에, 가격 하락이 발생한 것을 알 수 있다.

 

이 경우,

6의 index인 5를 3의 index인 6에 빼주면, 1이라는 기간 동안 가격 하락이 없었다는 것을 알 수 있다!

 

마찬가지로 6이 pop 되면 stack의 top은 (5,4)가 된다.

5는 3보다 작기 때문에 또 6-4 = 2를 통해 2라는 기간 동안 가격 하락이 없었다는 것을 알 수 있다!

 

(4,3)도 3보다 크기 때문에 가격 하락이 이루어졌다.

6-3 = 3으로 3이라는 기간동안 가격 하락이 없었다는 것을 알 수 있다.

 

마지막으로 (3,2)는 가격하락이 없었기 때문에 (3,6)을 push 해준다.

 

배열에 더 이상의 수가 존재하지 않기 때문에 price.length에 스택의 idx들을 빼주고 -1을 해주면 남은 스택의 가격들의 가격 하락 기간을 알 수 있다!

 

 

전체 코드(성공) :

import java.util.*;
class Solution {
    static class Node{
        int p;
        int idx;
        Node(int p, int idx){
            this.p = p;
            this.idx = idx;
        }
    }
    
    public int[] solution(int[] prices) {
        int[] ans = new int[prices.length]; // 정답 배열
        
        Stack<Node> stack = new Stack<>(); 
        
        for(int i=0; i<prices.length; i++){ // 모든 가격 순차 탐색
            int price = prices[i]; // 현재 가격
            
            while(!stack.isEmpty()){ 
                Node top = stack.peek();
                if(top.p <= price) break;
                    
                ans[top.idx] = i-top.idx; // 가격 하락 기간을 계산해준다.
                stack.pop(); // 기간 계산이 완료되었기 때문에 pop 해준다.
            }
                
            stack.push(new Node(price,i)); // 새로운 현재 가격을 추가해준다. 스택에서 가장 높은 수이다.
        }
        
        while(!stack.isEmpty()){ // 단 한번도 가격 하락이 없었던 스택의 남은 수들의 기간을 계산해준다.
            Node top = stack.pop();
            ans[top.idx] = prices.length-top.idx-1;
        }
        
        return ans;
    }
}

 

내 주식은 언제 오를까..