프로그래머스 - 주식가격(Java)

문제 설명

초 단위로 기록된 주식 가격이 담긴 prices 배열이 주어진다.

각 시점의 주식 가격이 가격이 떨어지지 않고 얼마나 오래 유지되었는지를 구하는 문제이다.

예를 들어,

prices = [1, 2, 3, 2, 3]

이라면 첫 번째 가격 1은 마지막까지 가격이 떨어지지 않으므로 4초 동안 유지된다.

---

접근 방법

• i → 현재 기준이 되는 주식 가격
• j → i 이후의 주식 가격을 비교하는 대상

for (int i = 0; i < prices.length; i++) {
    for (int j = i + 1; j < prices.length; j++) {

현재 가격이 이후 가격보다 크지 않다면 answer[i]를 1 증가시킨다.

answer[i]++;

이후 가격이 작아졌다면 가격이 떨어진 것이므로 종료.

if (prices[i] > prices[j]) {
    break;
}

---

풀이 순서

1. prices의 길이만큼 answer 배열을 생성한다.
2. i를 기준으로 현재 주식 가격을 정한다.
3. j를 i + 1부터 시작하여 이후의 가격과 비교한다.
4. 가격이 떨어지지 않았다면 answer[i]를 1 증가시킨다.
5. 현재 가격보다 이후 가격이 작아지면 break하여 비교를 종료한다.
6. 모든 가격에 대해 위 과정을 반복한다.
7. 완성된 answer 배열을 반환한다.

---

최종 코드

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

스택활용 코드

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

실행결과

---

참고 자료

• [프로그래머스] 주식가격 - java (Stack 활용)