[프로그래머스] 주식 가격- python[ Stack ]

[level 2] 주식가격 - 42584

문제 링크

성능 요약

메모리: 17 MB, 시간: 23.04 ms

구분

코딩테스트 연습 > 스택／큐

채점결과

Empty

문제 설명

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

제한사항

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

입출력 예

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.

나의 풀이

처음 든 생각은 주식 가격이 떨어졌을 때만 조건으로 삼으면 되겠다는 생각이었다.

가격이 오르거나 같았을 때는 스택에 쌓는다.(그럼 점점 큰 값이 쌓이는 구조일 것임 ex)prices = [1,2,3,2,3] 이 입력일 때는 [1,2,3]까지 쌓인 후 2를 만났을 때 스택에 있던 3이 사라지고, [1,2]가 남는 구조)

그런식으로 temp라는 배열에 스택을 쌓아주고, 가격이 낮아졌을 때만 temp의 마지막 값과 반복비교를 해주어 answer 배열에 저장해준다.

마지막으로 temp 배열에 남아있는 애들은 끝까지 가격이 떨어지지 않은 값들이기 때문에 전체 시간에서 저장된 시간 -1 을 수행하여 저장해준다. 

def solution(prices):
    
    answer = [0 for _ in range(len(prices))]
    temp = []
    for i in range(len(prices)-1):
        temp.append([prices[i],i])
        while temp and temp[-1][0] > prices[i+1]: 
            val, time = temp.pop()
            answer[time] = i-time +1
    for t in temp:
        answer[t[1]] = len(prices) - t[1]-1
    return answer