[프로그래머스/Python] 알고리즘고득점Kit-스택/큐-주식가격

📌 문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

 

 

📌 풀이과정 

🍀  1번째 시도: 정확성 pass 효율성 fail 

• 효율성 문제인 이유: 파이썬에서 슬라이싱은 O(N)의 시간복잡도를 가지고 있기 때문이다. 
• 그리고 시간 계산에서 문제가 계속 있었다. 어느 때는 1을 안 더하고, 언제는 더하고..  그래서 이 방식이 틀렸구나 싶었다. 

def solution(prices):
    answer = []
    reversed_p = prices[::-1]
    #print(reversed_p)
    for i, now_p in enumerate(reversed_p):
        cnt = 0
        tmp = reversed_p[:i]
        #print(tmp)
        for past_p in tmp[::-1]:
            if past_p >= now_p:
                cnt += 1
            else:
                cnt += 1
                break 
        answer.append(cnt)
        #print(answer)
                
    return answer[::-1]

 

 

🍀 2번째 시도: 구글링 후 pass 

• 이걸 큐로 어떻게 구현하지 좀 어렵게 생각했다. 
  • 하나 pop하고 뒤로 보내고를 계속 반복해야 한다고 생각했다. 
• 그래서 구글링해보니까 prices.pop(0)에 대해서 남은 price 값들과 비교하면 되는 걸 발견했다.

from collections import deque
def solution(prices):
    answer = []
    queue = deque(prices)
    while queue:
        price = queue.popleft()
        sec = 0 
        for q in queue: 
            sec += 1
            if price > q: break 
        answer.append(sec)
    
    return answer

 

 

 

📌 풀이코드 

from collections import deque
def solution(prices):
    answer = []
    queue = deque(prices)
    while queue:
        price = queue.popleft()
        sec = 0 
        for q in queue: 
            sec += 1
            if price > q: break 
        answer.append(sec)
    
    return answer