프로그래머스 파이썬 stack 주식가격

프로그래머스 링크: https://programmers.co.kr/learn/courses/30/lessons/42584

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

 

 

초반에는 prices의 길이가 너무 길어서 브루트포스가 될까? 라는 생각으로 무작정 짜보았다.

 

 

for i in range(len(prices)):
    for j in range(i,len(prices)):
        if i == j:
            continue
        else:
            if prices[i] <= prices[j]:
                answer[i] += 1
            else:
                answer[i] += 1
                break
print(answer)

그냥 대충 재현해봤다. 이렇게하면 비슷하게 나온다. 

 

하지만 효율성이 완전 끝내주게 쓰레기여서 다시 방법을 찾았다.

스택에 쌓아 올리는 형식으로 바꾸게 되었다.

 

 

answer 값에 배열을 미리 저장하고 나서

 

prices에 대한 enumerate for in 문을 작동해서 배열의 시간대와 값을 따로 불러낸다.

스텍이 존재하지 않으면 우선 스택에 append하고 

만약 스택이 존재하고 스택의 마지막 값이 지금 불러온 값보다 크다면 가격이 내려가는 것이기에

stack.pop()을 작동해서 stack[-1][0]을 가져와서 내 시간에서 뺀 값이 결과값이다.

 

만약 끝까지 삭제가 안된값이 있다면 끝난후 [prices의 길이값 - 장소값 - 1] 을 계산하면 된다.

 

 

def solution(prices):
    answer = [0]*(len(prices))
    stack=[]

    for t,i in enumerate(prices):
        while stack and stack[-1][1] > i:
            v = stack.pop()
            answer[v[0]] = t - v[0]

        stack.append([t,i])

    while stack:
        time = stack.pop()[0]
        answer[time] = len(prices)-time-1

    
    return answer