[프로그래머스 / Python] 주식가격

🧩 문제 

 

🌱 풀이과정

1️⃣ 이중 for문 사용하기 - O(N^2)

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
            else:
                time += 1
                break
        answer.append(time)
        
    return answer

다른 풀이를 보는데 나랑 비슷한 코드에 이런 코멘트가 달려있었다.

네엡 ... 😅 그렇다면 문제의도에 맞게 스택을 활용해 풀어보겠습니다 ... 

 

 

2️⃣ deque 사용하기 - O(N^2)

from collections import deque

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

 

둘다 시간복잡도가 O(N^2)이기는 하지만, 효율성 테스트에서의 시간이 전체적으로 줄어들었다 ..!

이유는 전자의 경우 최악의 경우 n*n번 탐색하지만, 후자는 while문에서 n번, for문에서 n-1 번으로 총 n*(n-1)번 탐색하기 때문인 것 같다. 

 

내 머리로는 이것이 최선일 것 같다 😵‍💫

 

👩🏻‍💻 전체코드 

from collections import deque

def solution(prices):
    answer = []
    # deque로 변환
    prices = deque(prices)
    
    while prices:
        time = 0
        # 맨 앞 원소를 pop
        left_price = prices.popleft()
        # 그 다음 원소부터 비교
        for right_price in prices:
            if left_price > right_price:
                time += 1
                break
            else:
                time += 1
        answer.append(time)
    
    return answer