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

문제 유형

스택/큐

 

문제

프로그래머스

 

문제풀이(큐 이용)

1차 시도(6.7)

def solution(prices):
    answer = []
    
    while len(prices) > 0:
        first_price = prices.pop(0)
        second = 0
        
        if len(prices) == 0:
            answer.append(0)
            break
            
        for i in range(len(prices)):
            if first_price <= prices[i]:
                second += 1
            else:
                if i == 0:
                    second += 1
                    break
        answer.append(second)
            
    return answer

 

2차 시도(통과)

• 이중 for문 사용하여 i가 하나씩 빼는 듯한 느낌을 줌
• i <= j일때 second += 1, i > j (3에서 2되는 경우)는  second += 1 만들고 멈추기

def solution(prices):
    answer = []
    
    for i in range(len(prices)):
        second = 0
        for j in range(i+1,len(prices)):
            if prices[i] <= prices[j]:
                second += 1
            # [1,2,3,2,3]일 경우 3->2일 때 1초간 가격이 떨어지지 않는 것으로 봄
            # else로 조건 걸어준 후, break
            else:
                second += 1
                break
        answer.append(second)
    return answer

 

다른 사람들의 풀이

1) (큐) 비슷한 코드

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

2) (큐) deque 이용

• for i in range(len(prices)) -> 메모리에 적재하지 않고 순회 (속도면에서 더 빠름)
• for i in prices -> 새로운 공간을 만들어서 할당

from collections import deque
def solution(prices):
    answer = []
    prices = deque(prices)
    while prices:
        c = prices.popleft()

        count = 0
        for i in prices:
            if c > i:		# c값이 더 크면 1만 더하고 멈추기
                count += 1
                break
            count += 1

        answer.append(count)

    return answer

3) (스택) 3,4번 유사

def solution(p):
    ans = [0] * len(p)
    stack = [0]
    for i in range(1, len(p)):
        if p[i] < p[stack[-1]]:
            for j in stack[::-1]:
                if p[i] < p[j]:
                    ans[j] = i-j
                    stack.remove(j)
                else:
                    break
        stack.append(i)
    for i in range(0, len(stack)-1):
        ans[stack[i]] = len(p) - stack[i] - 1
    return ans

4) (스택) 

def solution(prices):
    stack = []		# stack에 [순서, 해당 숫자] 2차원 배열 형태 
    answer = [0] * len(prices)
    
    for i in range(len(prices)):
        if stack != []:
            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

 

 

reference

- Stack

[Python 자료구조] 스택(Stack)