[42584] 주식가격

✔ 주식가격

[프로그래머스 42584]

문제 분석하기

이중 for문 또는 스택을 활용

증가하거나 같지 않고 떨어질 경우 answer에 넣고, 증가하거나 같을 경우 stack에 인덱스를 넣도록 함

prices	price	stack	return (answer)
[1, 2, 3, 2, 3]		[]	[0, 0, 0, 0, 0]
	1이므로 인덱스 0 삽입	[0]	[0, 0, 0, 0, 0]
	1 <= 2이므로 인덱스 1 삽입	[0, 1]	[0, 0, 0, 0, 0]
	2 <= 3이므로 인덱스 2 삽입	[0, 1, 2]	[0, 0, 0, 0, 0]
	3 > 2이므로 인덱스 2 삭제	[0, 1]	i - stack.peek() = 3 - 2 = 1 [0, 0, 1, 0, 0]
	2 <= 2이므로 인덱스 3 삽입	[0, 1, 3]	[0, 0, 1, 0, 0]
	2 <= 3이므로 인덱스 4 삽입	[0, 1, 3, 4]	주식의 길이 - stack.peek() - 1 = 5 - 4 - 1 = 0 [0, 0, 1, 0, 0]
		[0, 1, 3]	주식의 길이 - stack.peek() - 1 = 5 - 3 - 1 = 1 [0, 0, 1, 1, 0]
		[0, 1]	주식의 길이 - stack.peek() - 1 = 5 - 1 - 1 = 3 [0, 3, 1, 1, 0]
		[0]	주식의 길이 - stack.peek() - 1 = 5 - 0 - 1 = 4 [4, 3, 1, 1, 0]

손으로 풀어보기

1. for문을 돌면서 주식이 떨어질 경우 answer에 떨어지지 않은 기간 넣기
   주식이 동일하거나 증가하는 경우 stack에 인덱스를 넣기
   • i - stack.peek()
2. 모든 주식을 돈 후 스택에 남아있는 값은 끝까지 주식이 떨어지지 않은 경우이므로
   stack에 빌 때까지 answer에 떨어지지 않은 기간 넣기
   • 주식의 길이 - stack.peek() - 1

슈도코드 작성하기

prices(주식가격이 담긴 배열)
answer(가격이 떨어지지 않은 기간)
stack(주식을 담을 스택)
for(prices만큼) {
    while(스택이 비어있지 않으면서 주식이 떨어지는 동안) {
        answer[stack.peek()] = i - stack.peek()
        stack.pop()
    }
    stack.push(i)
}
while(스택이 빌 때까지) {
    answer[stack.peek()] = prices.length - stack.peek() - 1
    stack.pop()
}
answer 반환

코드 구현하기

/**
 * 42584) 주식가격
 */
public class K004_42584 {
    // prices(주식가격이 담긴 배열)
    public int[] solution(int[] prices) {
        // answer(가격이 떨어지지 않은 기간)
        int[] answer = new int[prices.length];
        // stack(주식을 담을 스택)
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < prices.length; i++) {
            // 스택이 비어있지 않으면서 주식이 떨어지는 동안
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                // answer에 떨어지지 않은 기간 넣기
                answer[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            // 주식이 동일하거나 증가하는 경우 stack에 인덱스를 넣기
            stack.push(i);
        }
        // 모든 주식을 돈 후
        // 스택이 빌 때까지
        while (!stack.isEmpty()) {
            // 끝까지 주식이 떨어지지 않은 경우
            // answer에 떨어지지 않은 기간 넣기
            answer[stack.peek()] = prices.length - stack.peek() - 1;
            stack.pop();
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K004_42584 solution = new K004_42584();

        int[] prices = { 1, 2, 3, 2, 3 };
        int[] result = solution.solution(prices);

        System.out.println(Arrays.toString(result));
    }
}