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

1차 시도

def solution(prices):
    answer = []
    cnt=0
    
    while prices:
        sec=prices.pop(0)
        cnt=0
        for i in range(0,len(prices)):
            if sec <= prices[i]:
                cnt +=1
        answer.append(cnt)
        
    
    
    return answer

틀린 이유

• if sec <= prices[i] 가 아닌 경우, 즉 주식가격이 내린 경우에 결과값이 0이 되기 때문입니다.

2차시도 (정답 맞춤 / 효율성 테스트는 실패)

def solution(prices):
    answer = []
    cnt=1
    prices.pop(len(prices)-1)
    
    while prices:
        tmp=prices.pop(0)
        cnt=1
        for i in prices:
            if tmp<=i:
                cnt+=1
            else:                
                break
        answer.append(cnt)
        
    answer.append(0)              
                
            
    return answer

• 어느 부분에서 효율이 떨어지는 걸까요? ㅠㅠ
• 큐 개념에서 pop(0)을 쓸 때 시간복잡도가 O(n)이라고 합니다. 하긴 pop(0)을 하면 나머지 원소들이 모두 이동을 해야 하니깐 그런가 봅니다.

다른 분의 풀이

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

아이디어

• 굳이 스택/큐 pop, append를 사용하지 않습니다.
• answer = [0] * len(prices)로 초기 결과값을 세팅하고 시작합니다.
• 그러면 마지막 주식가격은 for j 문을 거치지 않으므로 자연스레 결과값이 0이 됩니다.
• index는 시간(1초씩 증가), 값은 그 시간의 주식가격이 떨어지지 않는 기간입니다. 

파이썬개념

리스트에 동일한 값 할당하는 법

answer = [0] * len(prices)