주식가격

📖 스택/큐 > 주식가격

📖What I thought

1. stack의 전형적인 문제
2. stack 안에는 주식 가격이 최초로 떨어지는 시점을 찾지 못한 가격의 idx == 늘 stack의 top에 있는 가격 ⇐ 현 가격 일 때만 stack에 넣음
3. 만약 stack의 top에 있는 가격 > 현 가격이라면 stack의 top의 주식 가격이 최초로 떨어진 것 → 답 갱신해주기
4. 3번을 2번이 될 때까지 반복

📖풀이

📎Stack #1

def solution(prices):
    sec = [0 for _ in range(len(prices))]
    st = []
    
    for i in range(0, len(prices)):
        while st and prices[st[-1]] > prices[i]:
            j = st.pop()
            sec[j] =  i-j
            
        st.append(i)
        
    while st:
        x = st.pop()
        sec[x] = len(prices)-1 -x
    
    return sec

📎Stack #2

def solution(prices):
    sec = [i for i in range(len(prices)-1, -1, -1)] # 각 시점의 최대 가격이 떨어지지 않은 기간
    st = [] # 가격이 떨어지지 않고 있는 시점의 idx 넣어줌
    
    for i in range(0, len(prices)):
        # 가격이 떨어졌을 때
        while st and prices[st[-1]] > prices[i]:
            j = st.pop()
            sec[j] = i - j # 현재 시점과 해당 가격의 시점 차 (가격 방어 성공 기간)
        
        st.append(i)
            
    return sec

• loop를 한 번 다 돌았는데도 stack에 남아있는 값들 → 해당 시점에서 끝까지 가격이 떨어지지 않음 == 해당 시점에서 최장 기간 가격 유지
• 그럼 처음 가격이 떨어지지 않는 기간을 담은 리스트를 만들 때 각 시점에서 가격이 떨어지지 않을 수 있는 최대 시간을 담으면 마지막에 stack을 순회하지 않아도 됨

📖What I learned

stack 안에는 주식 가격이 최초로 떨어지는 시점을 찾지 못한 가격의 idx == 늘 stack의 top에 있는 가격 ⇐ 현 가격 일 때만 stack에 넣음

1. 이런 개념의 stack 문제가 정말정말 많이 출제되므로 기억 (앞의 값 & 뒤의 모든 값들과 대소를 비교)

📖관련 지식

📎Stack