프로그래머스 Lv.2) 주식가격 (Stack & Queue)

주식가격

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

풀이

프로그래머스 고득점 Kit 중에 Stack, Queue에 해당하는 문제다. 이 문제도 전에 풀었지만, 포스팅을 한 적이 없어서 새롭게 포스팅을 한다.

우선 문제의 조건을 살펴보면, 특정 날의 주가가 이후에 가격이 떨어지지 않은 기간을 구하는 문제이다.

 

먼저, 첫번째로 풀었던 방법에 대해 기억나는대로 되짚어 본다면

반복문을 돌면서 특정 날의 주가에 대해 주가 하락 시점을 Stack에 저장한 것 같다.

하락 시점 날이 저장된 stack에서, 저장된 시점들에 대해 전체 진행 날짜 - 하락 날짜를 답에 저장한 것 같다.

 

Stack에 각 주가의 하락 시점을 저장 ~> 전체 날짜 - 하락 시점을 답에 저장

---

오늘 푼 방법은 이중 반복문을 통해 값을 바로 저장해주었다.

반복문이 진행되면서 저장된 답 +1을 진행하면서, 주가가 하락하는 시점에 반복문을 끝내주었다.

처음 풀었던 코드는 고득점 Kit에 Stack과 Queue과 명시되어 있어서, 자료구조를 최대한 활용하고자 Stack으로 풀었던 것 같다.

하지만, 고득점 Kit에 신경쓰지 않고, 오늘 푼 방법이 더 효율적이고 코드가 짧다는 것에 만족한다.

 

로직

1. 각 주가마다 남은 날에 대해 for문을 돌면서 answer을 증가시켜준다.

2. 이후, 주가 하락 시점인지 확인하고, 맞다면 반복문을 종료한다.

 

 

코드 1

 

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int len = prices.length;
        int[] answer = new int[len];

        Stack<int[]> stack = new Stack<>();

        // 주가 하락시점 저장
        for(int i=0; i<len; i++) {
            int[] tmp = {i, prices[i]};
            if(stack.isEmpty()) {
                stack.add(tmp);
            } else {
                while(stack.peek()[1] > prices[i]) {
                    int[] popStock = stack.pop();
                    answer[popStock[0]] = i - popStock[0];
                    if(stack.isEmpty()) {
                        break;
                    }
                }
                stack.add(tmp);
            }
        }

        while(!stack.isEmpty()) {
            int[] tmp = stack.pop();
            answer[tmp[0]] = len - tmp[0] -1;
        }

        return answer;
    }
}

 

코드 2

 

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