[Java] 주식가격 - Lv2 프로그래머스 (스택/큐)

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

프로그래머스

 

스택을 활용한 문제를 더 풀어보기 위해 관련 카테고리 문제를 찾아서 풀어봤음.

 

 

풀이

---

 

https://mag1c.tistory.com/103

스택(Stack)

 

스택을 이용하여 풀어야 하는걸 앎에도 일단 단순하게 짜봤음..

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-1; j++) {
            if(prices[i] > prices[j]) {
                answer[i] = j-i;
                break;
            }
        }
    }
    for(int i=0; i<answer.length; i++) {
        if(answer[i] == 0) {
            answer[i] = (answer.length-1) - i;
        }
    }

    return answer;
}

단순 이중 for문으로 하나씩 들고와서 계속비교했음

 

 

 

아래는 스택 사용한 풀이

prices의 idx값을 stack에 넣고 다음 값들과 계속 비교

LIFO구조이기 때문에 큰 값들이 계속 pop되어 나간다.

직전에 풀어본 stack문제 때문에 쉽게 접근 가능했다.

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

    Stack<Integer> stack = new Stack<>();
    for(int i=0; i<prices.length; i++) {
        while(!stack.empty() && prices[stack.peek()] > prices[i]) {
            int idx = i-stack.peek();
            answer[stack.pop()] = idx;
        }
        stack.push(i);
    }

    int size = stack.size();
    int idx = 0;
    for(int i=0; i<size; i++) {
         idx = stack.pop();
         answer[idx] = prices.length-1-idx;
    }
    return answer;
}