📌문제

---

📌나의 코드

❌ 1. while & 리스트(pop(0))

def solution(prices):
    answer = []
    while prices:
        time = 0
        now = prices.pop(0)
        for i in prices:
            if now > i:
                time += 1
                break
            if now <= i:
                time += 1
        answer.append(time)
    return answer

⭕ 2. 이중for문

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

⭕ 3. while & deque(popleft())

from collections import deque

def solution(prices):
    answer = []
    prices = deque(prices)
    while prices:
        time = 0
        now = prices.popleft()
        for i in prices:
            if now > i:
                time += 1
                break
            else:
                time += 1
        answer.append(time)
    return answer

⇒ deque의 popleft와 while을 사용하는 게 효율성 테스트에서 시간이 빨랐다.

---

📌다른 사람의 풀이 (가장 효율적)

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    for i in range(len(prices)):
        while stack != [] and stack[-1][1] > prices[i]:  
            past, _ = stack.pop()                        
            answer[past] = i - past                      
        stack.append([i, prices[i]])                     
    
    for i, s in stack:   
        answer[i] = len(prices) - 1 - i                  
    return answer

1. 스택에 [현재 시간, 가격] 추가
2. 루프를 돌며 스택의 마지막 가격이 현재 가격보다 크면, 스택에서 마지막 가격을 빼고 그 가격이 저장된 시간을 과거 시간(past)으로 저장
3. answer의 '가격이 저장된 시간'에 해당하는 자리에 가격이 떨어지지 않았던 시간 저장, (현재 시간 - 이전 가격이 저장된 시간)
4. 루프를 다 돌고 스택에 끝까지 떨어지지 않은 가격들이 남으면 answer의 '가격이 저장된 시간'에 (총 가격의 개수 - 1 - 저장된 시간) 저장, 인덱스는 0부터 시작하고 지속시간이므로 자기자신을 빼야 한다.

---

📌배운 점

1. 리스트에서 pop(0)을 사용하는 것보다 덱의 popleft()가 더 빠르다.
2. 스택을 만들어서 하나의 변수로 두 개, 시간과 인덱스를 해결할 수 있다.
3. 자료구조를 이리저리 응용해보는 연습이 필요하다.