[프로그래머스][Level2][Java] 주식가격

문제

 

 

풀이코드

public int[] solution(int[] prices) {           //주식가격
    int[] answer = new int[prices.length];
    int count = 0;                              //주식이 떨어지는 시간 count
    for(int i = 0; i< prices.length;i++){
        count = 0;
        for(int j = i+1; j< prices.length;j++){ 
            count++;
            if(prices[i]>prices[j]){            //만약 앞의 값이 더 크면 반복문 탈출
                break;
            }
        }
        answer[i] = count;
    }
    return answer;
}

원래 내가 문제를 보자마자 생각한 방법이 이중 반복문을 사용해서 각각 prices들의 크기를 비교해서 푸는 것 이었는데

솔직히, 생각해놓고 이게 시간 복잡도가 O(n*n)이라서 문제의 테스트 케이스에 prices배열의 길이가 많이 크면 실패하겠다...라고 생각하고 풀었는데? 다 통과되서 좀 당황하긴 했다.

근데 이 문제가 스택/큐영역에 있는 문제라서 스택이나 큐를 사용해서 풀고 싶었는데 내 머리로는 도저히 방법을 모르겠어서 다른 분의 풀이를 참고했다.

public int[] solution(int[] prices) {
    int[] ans = new int[prices.length];
    Stack<Integer> stack = new Stack();

    for (int i = 0; i < prices.length; i++) {
        while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
            ans[stack.peek()] = i - stack.peek();
            stack.pop(); // 답을 구했기 때문에 stack에서 제거한다
        }
        stack.push(i);
    }

    while (!stack.isEmpty()) { // 값을 구하지 못한 index == 끝까지 가격이 떨어지지 않은 주식
        ans[stack.peek()] = prices.length - stack.peek() - 1;
        stack.pop();
    }

    return ans;
}

 

 while (!stack.isEmpty() && prices[i] < prices[stack.peek()]){
 	ans[stack.peek()] = i - stack.peek();
        stack.pop(); // 답을 구했기 때문에 stack에서 제거한다
 }

이 조건은 stack이 비어있지 않거나 감소하는 값이 등장한다면 주식이 감소한 시점이므로 stack에서 해당 인덱스를 제거하고 i(현재 주식의 감소 시점) - stack.peek(주식이 처음 들어간 시점) 값을 ans[stack.peek]값에 넣어준다

 

 for (int i = 0; i < prices.length; i++) {
        //while 부분
        
        stack.push(i);
    }

0번부터 n-1까지 반복문을 돌며 

prices[stack.peek]과 비교하여 주식이 감소하지 않았다면(while의 조건에 만족이 안되면)

stack에 시간 index를 push한다

 

그리고 나머지 부분은 주석에 설명이 잘 달려있어서 따로 설명이 필요없을 것 같다.

 

참조블로그

https://girawhale.tistory.com/7

[프로그래머스] 주식가격(Stack) - JAVA