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

 

문제 링크

코딩테스트 연습 - 주식가격 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 주식가격

 

풀이

prices[] 는 1초마다 바뀌는 가격입니다. 각 위치에서 몇 초 동안이나 가격이 내려가지 않았나 구하면 됩니다.

 

이 문제에도 순서가 존재하는데, prices 배열에 들어있는 순서대로 값이 바뀌고, 순서를 따라 가야합니다.

스택을 활용하면 될 것 같습니다.

Stack<Integer> S = new Stack<>();
S.push(0);

 

스택 S를 선언. S에는 인덱스 값이 들어가게 됩니다. 맨 첫번째 인덱스값= 0을 넣어줍니다.

 

 

for(int i=1;i<len;i++){
    while(!S.isEmpty() && prices[S.peek()] > prices[i]){ // 가격이 감소함.
        Integer peek = S.peek();
        ans[peek] = i-peek;
        S.pop();
    }
    // S.peek() <= prices[i]
    S.push(i);
}

S 에서 가져온 인덱스 값으로 prices에 대입해 가격을 알아올 수 있습니다.

for문에서 i번째 가격인 prices[i] 와 prices[S.peek()] 의 값을 비교하여 가격이 감소했다면,

S.peek() 는 인덱스를 의미하므로 S.peek() 인덱스에 i - peek 를 넣어주면 됩니다.

 

이게 무슨 말이냐면 for문의 i는 인덱스 이기도 하지만 '시간' (몇 초가 지났느냐)을 의미하기도 합니다.

S 에 들어있는 값도 인덱스이면서 시간 을 의미합니다.

따라서 i - peek 의 값은 두 값들의 시간 차이를 나타내게 되고, 스택에는 가격이 높은 값들의 인덱스만 쌓게 됩니다.

따라서 S의 위쪽에서 뽑아온 인덱스에, i - peek 만큼의 시간차이가 발생하게 되는 것입니다.

 

 

소스코드

public int[] solution(int[] prices) {
    int len = prices.length;
    int[] ans = new int[len];
    Stack<Integer> S = new Stack<>();
    S.push(0);

    for(int i=1;i<len;i++){
        while(!S.isEmpty() && prices[S.peek()] > prices[i]){ // 가격이 감소함.
            Integer peek = S.peek();
            ans[peek] = i-peek;
            S.pop();
        }
        // S.peek() <= prices[i]
        S.push(i);
    }

    while(!S.isEmpty()){
        int peek = S.peek();
        ans[peek] = len-1-peek;
        S.pop();
    }
    return ans;
}