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

📑 1. 문제설명

---

💡 2. 접근방식

이중for문

현재 인덱스에 있는 요소과 이후 모든 값을 비교하면서 현재 요소가 비교하고 있는 요소보다 커지면 break;를 걸어준다.

그 전까지는 answer[i]++을 해 준다. 

현재 요소가 더 크다는 말은 이후에 가격이 떨어졌다는 것을 의미하기 때문이다. 

현재 요소가 비교하는 값과 같거나 더 적다면 가격이 유지되거나 오른 것이다.

스택(Stack)

근데 이게 스택/큐 문제라는데 스택으로는 어떻게 풀지? 오잉

그래서 다른 사람들은 어떻게 푸는 지 좀 찾아 봤다. 

그냥 이중포문으로 푸는게 더 간단한 것 같다.

 

prices의 인덱스를 스택에 넣어 주면서 현재 가격과 스택의 가장 위 가격을 비교해준다. 

스택이 비어있지 않고, 현재 가격이 스택의 가장 위 가격보다 작으면 

바로 가격이 떨어진 지점에서의 시간을 계산하고, stack.pop()을 해 준다. 

만약 현재 가격이 스택 맨 위 가격보다 높다면 스택에 현재 인덱스를 넣어 주는 작업을 반복한다.

 

그러면 가격이 떨어진 지점에서 걸린 시간이 먼저 answer[i]에 채워 진다.

스택 안에 남아있는 인덱스들은 마지막까지 가격이 떨어지지 않은 것이기 때문에 각 가격이 끝까지 떨어지지 않은 기간을 따로 구해준다.

answer[stack.peek()] = prices.length - stack.peek() - 1;

 

여기서 -1을 해 주는 이유는 마지막 날짜는 이미 계산된 것이므로 제외해 주는 것이다. 주어진 가격의 "기간"은 해당 가격이 떨어지지 않고 유지된 기간을 의미하는데, 끝날 때까지 유지된 상태를 포함하면 안 되기 때문에 마지막 날짜를 제외하고 계산한다.

---

⭐ 3. 코드

이중 for문

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;
    }
}

Stack

import java.util.Stack;
class Solution {
    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.isEmpty() && prices[i] < prices[stack.peek()]) {
                // 스택이 비어있지 않고, 현재 가격이 스택의 가장 위 가격보다 작으면
                // 스택에서 하나씩 꺼내면서 계산
                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;
    }
}

---

👉🏻 4. 같은 유형 문제

[프로그래머스] (Java) 다리를 지나는 트럭 (스택/큐)

[프로그래머스] (Java) 프로세스 문제풀이 (스택/큐)

[프로그래머스] (Java) 올바른 괄호 문제풀이 (스택/큐)

[프로그래머스] (Java) 기능개발 (스택/큐)

[프로그래머스] (Java) 같은 숫자는 싫어 문제 풀이 (스택/큐)