[Programmers] 스택/큐.주식가격 / Stack

@Stack / 25m

생각보다 쉬우면서도 생각보다 까다로운 문제

 

 

문제 링크

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

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

 

구현 포인트

스택이 왜 필요한지에 대해 이해해야 한다.

물론 스택 없이도 풀 수는 있겠지만, 그러면 효율성이 떨어질 것이다 ㅜㅜ

 

스택에 들어가려면 스택이 비어있거나, 아니면 stack.peek() 값이 지금 넣으려는 값보다 항상 작아야 한다.

만약 스택의 top 값이 지금 넣으려는 값보다 크다면 지금 넣으려는 값보다 작거나 같은 값만 남아있을 때까지 stack에서 pop해준다.

 

입력 예제인 1,2,3,2,3을 예로 들어보자면

1	2	3	2	3	비고
stack.push(1)					현재 스택 1
	stack.push(2)				현재 스택 1, 2
		stack.push(3)			현재 스택 1, 2, 3
			스택에 들어있는 값(3) 보다 작다. 그러므로 stack.pop() 으로 3을 제거해준다		스택에서 3을 제거한 후 2를 넣어준다 현재 스택 1, 2, 2
				stack.push(3)	현재 스택 1, 2, 2, 3

 

그리고 for문을 한번 다 돌고 나서는

거꾸로 for문을 돌면서 answer가 비어있다면 그 칸에 시간을 넣어준다.

 

 

코드

import java.util.*;

public class 주식가격 {
	public static void main(String[] args) {
		System.out.println(Arrays.toString(solution(new int[] {1, 2, 3, 2, })));
	}

	public static int[] solution(int[] prices) {
		Stack<Integer> stack = new Stack<Integer>();
        int len = prices.length;
        int[] answer = new int[len];
        
        for (int i = 0; i < len; i++) {
			int temp = i, time = 1;
			while (!stack.isEmpty() && stack.peek() > prices[i]) {
				stack.pop();
				while (temp > 0 && answer[--temp] != 0) {
					time++;
				}
				answer[temp] = time++;
			}
			stack.push(prices[i]);
		}
        
        int time = -1;
        for (int i = len - 1; i >= 0; i--) {
            time++;
            if (answer[i] != 0) {
                continue;
            }
            answer[i] = time;
        }
        return answer;
	}
}

끝!