[스택] 프로그래머스 L2 '주식가격' (Python)

<문제 링크>

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

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

---

<문제 풀이>

1. prices의 길이만큼 시간이 지남
2. 스택으로 사용할 타이머 생성

<코드>

#1차시도 : 2,3,4,5,6,7,8,9,10 & 효율성테스트 실패

def solution(prices):
    stack = [0]   
    answer = [0] * len(prices)
    
    for i in range(1,len(prices)):
        if prices[i] < prices[stack[-1]]:  
            for j in stack[::-1]:   
                if prices[i] < prices[j]:   
                    answer[j] = 1  
                    stack.pop()
        stack.append(i)

    for i in stack:  
        answer[i] = len(prices) - (i+1)
    return answer

 

#prices = [1,2,3,2,3,1], answer = [5,4,1,2,1,0] 으로 고쳐서 해보기
#2차시도 : 성공

def solution(prices):
    stack = [0]   
    answer = [0] * len(prices)
    
    for i in range(1,len(prices)):
        if prices[i] < prices[stack[-1]]:   
            for j in stack[::-1]:   
                if prices[i] < prices[j]:   
                    answer[j] = i-j 
                    stack.pop()
        stack.append(i)

    for i in stack: 
        answer[i] = len(prices) - (i+1)
    return answer

 

#처음 했을 때의 참고자료
def solution(prices):
    timer = [0] * len(prices)   #배열 개수 지정
    stack = [0]   #주식값이 끝까지 안떨어진 주식값의 index들

    for i in range(1, len(prices)):
        if prices[i] < prices[stack[-1]]:   # 1<0, 2<1, 3<2... 값 비교.   현재값이 더 큰 경우(1초 뒤에 가격이 떨어짐)
            for j in stack[::-1]:               
                if prices[i] < prices[j]:           # 값이 떨어졌을 때보다 이전 값이 더 큰 경우 ([1,3,3,2,3]이면 2가 3,3들을 걸러냄)
                    stack.pop()                         # 맨 위의 값(가격이 떨어진 시간) 삭제
                    timer[j] = i-j                      # 가격이 떨어진 시간 = 값이 떨어진 시간(prices) - 값이 떨어질 시간(stack)
                else:                               # ([1,3,3,2,3]이면 2가 1을 만났을 때)                              
                    break                               # 스택 for문 빠져나감
        stack.append(i)   #[1,2,3]...초 후

    for i in range(0, len(stack)-1):
        timer[stack[i]] = len(prices) - stack[i] - 1   #스택 시간 = 총 시간 - 스택에 저장된 시간 - 1

    return timer

 

<고쳐야 할 점>

• 굳이 스택을 쓸 필요는 없다
• 다양한 경우의 수 생각해보기