[프로그래머스] 주식가격 (python)

출처 : 코딩테스트 연습 - 주식가격 | 프로그래머스 (programmers.co.kr)

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

풀이 방법

이중 for 문으로 0번 인덱스 부터 자신보다 작은 값이 나올 때까지 for 문을 돌며 작은 값이 나오면 정답에 추가해주는 방식의 간단한 방법으로 풀었다.

def solution(prices):
    answer = [0] * len(prices)
    for i in range(len(prices)-1):
        for j in range(i, len(prices)-1):
            if prices[i] >prices[j]:
                break
            else:
                answer[i] +=1
    return answer

더 좋은 풀이

위 코드 방식대로 풀면 시간 복잡도가 O(n^2)이 되어 효율적이지 못하다

다른 분들의 코드를 참고 하니 스택을 사용하는 방법이 있었다.

이 방식을 사용하면 시간 복잡도 amortized analysis에 의해O(n)만에 풀이를 할 수 있다.

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    for i in range(len(prices)):
    	## while문을 돌며 자신보다 작은 주식이 나올 때까지 처리
	    while len(stack) != 0 and prices[stack[-1]] > prices[i]:
		    answer[stack[-1]] = i - stack[-1]
		    stack.pop()
        ## 주식의 인덱스 저장
	    stack.append(i)
	## 마지막 까지 한번도 떨어지지 않은 주식 처리
    while len(stack) != 0:
	    answer[stack[-1]] = len(prices) - stack[-1] - 1
	    stack.pop()
    return answer