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

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

주식가격

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

문제 단순화

• prices 정수배열이 있다.
• 해당 배열의 n+x번째 요소가 n번째 요소보다 작을 때, 각 요소에서 처음으로 만나는 x들을 리스트로 리턴한다.
• x가 존재하지 않을 경우, 배열의 마지막 요소가 n+x번째가 된다.

문제풀이

• 현재 값보다 항상 큰 값을 저장하는 스택을 사용한다.
• answer는 prices의 마지막 요소를 n+x로 두어 결과를 미리 저장한다.[ x = (n+x)-n = (len(prices)-1)-n = len(prices)-1-n ]
• prices 요소를 순서대로 s의 최대값과 비교하여 작을 경우, 해당 s[-1]의 인덱스를 갖는 answer를 갱신한다.
• s[-1][0] = n, i = n+x 라 했을 때, x = (n+x)-n = i-s[-1][0]
• s[-1](최대값, 마지막값)을 빼내고, 다시 s[-1]보다 큰 값이 나오거나 s에 값이 없을 때까지 반복한다.
• 스택 연산이 끝나면, prices의 요소를 스택에 넣는다.
• 모든 prices의 요소를 탐색하고, 결과를 리턴한다.

팁

• 스택에 인덱스만 저장하고, prices에 인덱스를 넣어서 비교연산할 수 있다.
• 스택의 구조가 단순지며, 인덱스 탐색시간 줄어들어 코드 실행시간을 줄일 수 있다.
• 문제 단순화를 어떻게 설정하느냐의 따라 풀이방법이 다를 수 있다.

코드

def solution(prices):
    s = []
    answer = [len(prices)-1-n for n in range(len(prices))]

    for i,p in enumerate(prices):
        while s and s[-1][1] > p:
            answer[s[-1][0]] = i - s[-1][0]
            s.pop()
        s.append([i,p])

    return answer

or

def solution(prices):
    s = []
    answer = [len(prices)-1-n for n in range(len(prices))]

    for i,p in enumerate(prices):
        while s and prices[s[-1]] > p:
            answer[s[-1]] = i - s[-1]
            s.pop()
        s.append(i)

    return answer