[Python][Java] 스택_주식가격(LEVEL2)

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때,
가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

입출력 예 설명

1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.

문제풀이

[Python]
-> 고민해보기
현재의 시점의 주식 가격이 앞으로 n초까지 몇번 올랐는지 확인하려면,
전부 비교하는 것 외에 방법이 없음
앞으로 나아가야할 떄마다 탐색해야 할 개수가 줄어드는 구성이 될 것
--> 2중 for문 코드 작성

def solution(prices):
    size = len(prices)
    answer = [0] * size
    
    for i in range(size):
    	for j in range(i+1, size): #초가 지남에 따라, 탐색해야할 개수가 줄어듬
        	if prices[i] <= prices[j]: 
            	answer[i] += 1
            else:
            	answer[i] += 1
                break
    
    return answer

-> 스택(자료구조)의 필요성
몇초까지 상승세를 이어갔는지 여부 = 언제 떨어질지 물어보는 것,
따라서, 연속적으로 벌어지는 일에서 특정 시점을 끄집어낼 수 있다면,
"스택" 활용

def solution(prices):
	stack = []
    answer = [0] * len(prices)
    
    for i in range(len(prices)):
    	while stack and prices[stack[-1]] > prices[i]:
        	past = stack.pop()
            answer[past] = i - past
        stack.append(i)
        
    for i in stack:
    	answer[i] = len(prices) - 1 - i
        
    return answer

--> 앞으로 스택을 바라볼때, 장기적으로 DFS를 바라보는 관점도
'어떤 데이터를 넣을 것인지, 들어간 데이터는 어떤 의미인지, 데이터가 나올때는 어떤 상황'인지
이 3가지 상황에 맞게 정의하는 것이 스택의 사용방법이라 할 수 있다.

-> 자주 등장하는 유형(스택 활용가능 경우)
1) 괄호 문제(주어진 괄호가 모두 열리고 닫혔는지),
2) 수식 전환(전위, 중위, 후위 연산법),
3) 특정 흐름이 끊어지는 시점

[JAVA]
위치와 위치의 짝을 찾아야 하는 스택 문제
위치별로 들어있는 원소보다 더 작은 값이 처음으로 등장하는 위치

import java.util.Stack;

public 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[stack.peek()] > prices[i]) {
                int index = stack.pop();
                answer[index] = i - index;
            }
            stack.push(i);
        }
        
        while (!stack.isEmpty()) {
            int index = stack.pop();
            answer[index] = prices.length - index - 1;
        }
        return answer;
    }
}