주식가격 JAVA

문제

프로그래머스

1초단위로 주식가격이 적혀있는 prices[] 에서 주식가격이 떨어지는 시간을 각각 구한 배열 anwer를 구하는 문제이다.

예를 들어 prices = {1, 2, 3, 2, 3}는 answer = {4, 3, 1, 1, 0} 이다.

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

처음에는 이 문제가 스택 부분에 있어서 스택에 집착해 문제를 해결하였다. 그결과가 아래 코드이다.

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer>stack = new Stack<>();
        int[] answer = new int[prices.length];
        int time = 0;
        int temp_time=0;
        int temp = -1;
        for(int i=prices.length-1;i>=0;i--){
            if(stack.isEmpty()){
                stack.push(prices[i]);
                answer[i]=time;
            }
            else if(stack.peek()>=prices[i]){
                if(temp>= prices[i])answer[i]=time;
                else answer[i]=temp_time;
                stack.push(prices[i]);
            }
            else if(stack.peek()<prices[i]){
                temp = stack.peek();
                while(!stack.isEmpty())stack.pop();
                stack.push(prices[i]);
                temp_time=1;
                answer[i] = temp_time;
            }
            temp_time++;
            time++;
        }        
        return answer;
    }
}

여러 경우의 수를 다 생각해 말 그대로 구현한 것이다. 결과는 틀렸다. 

뭔가 공식이 있을 거 같은데 생각을 못했다.

다음에는 단순하게 이중 for문을 돌려서 생각해봤다.

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        int []answer = new int[prices.length];
        for(int i=0;i<prices.length;i++){
            for(int j=i+1;j<prices.length;j++){
                answer[i]++;
                if(prices[i]>prices[j])break;
            }
        }
        return answer;
    }
    
}

prices[] 길이가 최대 100000이므로 최악의 경우 100억을 탐색하므로 시간초과가 날것이다.

다시 스택으로 돌아와 공식을 생각해봤다.

https://girawhale.tistory.com/7

위 블로그를 참고하였다.

핵심은 스택에 가격을 넣는 것이 아니라, 가격의 시점을 넣는 것이다.

그렇게 넣어주면 시간 계산 하기도 편하기도 하고 문제를 수월히 해결할 수 있었다.

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer>stack = new Stack<>();
        int []answer = new int[prices.length];
        for(int i=0;i<prices.length;i++){
            if(stack.isEmpty())stack.push(i);
            else if(prices[stack.peek()] <= prices[i]){ //주식가격이 오르는 상황
                stack.push(i);
            }
            else if(prices[stack.peek()]>prices[i]){ //주식가격이 하락하는 상황
                while(!stack.isEmpty() && prices[stack.peek()]>prices[i]){
                    answer[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }
        while(!stack.isEmpty()){
            answer[stack.peek()] = prices.length-stack.peek()-1;
            stack.pop();
        }
        
        return answer;
    }
    
}

스택에 element를 넣을 때 좀더 생각을 깊이하고 넣어야 할것 같다. 

생각의 전환을 잘해야한다.