[프로그래머스, python3] 주식가격(이중 for문, Stack)

[프로그래머스, python3] 주식가격
난이도	Level 2
분류	스택/큐
programmers.co.kr/learn/courses/30/lessons/42584

---

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.

---

소스코드 

풀이1: 이중 for문

• 이전 prices가 현재 prices보다 크거나(=가격이 떨어졌다면) 또는 현재 탐색중인 index가 마지막 index라면 결과값 + 1을 하고 빠져나온다.
• 이전 prices가 현재 prices보다 작거나 같다면 가격이 유지되거나 오른것이므로 결과값 + 1을 하고, 다음 index를 탐색한다.
• 이중 for문의 경우 시간 복잡도가 크다. (O(n^2))

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

---

def solution(prices):
    # 모든 시점의 prices가 떨어지지 않았을 때, [4,3,2,1,0]
    answer = [len(prices)-1-x for x in range(len(prices))]
    stack = []
    
    for i in range(len(prices)):
        while stack:
            # 주식 가격이 떨어졌다면
            if prices[stack[-1]] > prices[i]:
                j = stack.pop() # stack[-1]
                answer[j] = i - j
            else:
                break
        stack.append(i)
 
    return answer

from collections import deque
 
def solution_stack(prices):
    # 모든 시점의 prices가 떨어지지 않았을 때, [4,3,2,1,0]
    answer = [len(prices) - 1 - x for x in range(len(prices))]
    stack = []
    print(f"prices: {prices}")
    print(f"answer: {answer}, stack: {stack}")
 
    for i in range(len(prices)):
        print('-' * 40)
        print(f"i: {i}, stack: {stack}")
        while stack:
            # 주식 가격이 떨어졌다면
            print(f"prices[stack[-1]]: {prices[stack[-1]]}, prices[i]: {prices[i]}")
            if prices[stack[-1]] > prices[i]:
                j = stack.pop()  # stack[-1]
                answer[j] = i - j
            else:
                break
        stack.append(i)
    print('-' * 40)
    return answer
 
if __name__ == "__main__":
    print('-' * 40)
    prices = [1, 2, 3, 2, 3]
    correct_answer = [4, 3, 1, 1, 0]
 
    answer = solution_stack(prices)
    print('answer :' , answer, '/ correct_answer :' , correct_answer)
    if correct_answer == answer:
        print(f'테스트를 통과하였습니다.')
    else:
        print(f'테스트를 통과하지 못했습니다.')
    print('-' * 40)
 
 
 
----------------------------------------
prices: [1, 2, 3, 2, 3]
answer: [4, 3, 2, 1, 0], stack: []
----------------------------------------
i: 0, stack: []
----------------------------------------
i: 1, stack: [0]
prices[stack[-1]]: 1, prices[i]: 2
----------------------------------------
i: 2, stack: [0, 1]
prices[stack[-1]]: 2, prices[i]: 3
----------------------------------------
i: 3, stack: [0, 1, 2]
prices[stack[-1]]: 3, prices[i]: 2
prices[stack[-1]]: 2, prices[i]: 2
----------------------------------------
i: 4, stack: [0, 1, 3]
prices[stack[-1]]: 2, prices[i]: 3
----------------------------------------
answer : [4, 3, 1, 1, 0] / correct_answer : [4, 3, 1, 1, 0]
테스트를 통과하였습니다.
----------------------------------------
 
Process finished with exit code 0