#5. stack & queue

스택 & 큐 자료구조란?

데이터를 순차적으로 쌓아나가는 선형 자료구조

• 스택: 들어온 순서대로 쌓고, 맨 나중에 들어온 데이터 먼저 꺼냄 , LIFO (Last In First Out)
  • 설거지
  • 괄호 짝맞추기
  • 웹사이트 뒤로가기
• 큐: 들어온 순서대로 쌓고, 먼저 들어온 데이터 먼저 꺼냄 ,FIFO (First In First Out)
  • 맛집 줄서기
  • 프린터 출력 순서 등 순서대로 처리해야하는 업무에 적용 

스택과 큐를 사용하는 문제들은 보통 리스트에 값을 차례로 쌓다가 특정 값을 마주칠 때 하나씩 pop() 해주는 문제이다.

대표적인 문제 예시로는 괄호 짝맞추기 문제가 있다.

 

문제를 풀이 컨셉은 "(" 괄호가 들어오면 스택에 쌓아주다가 ")" 괄호가 들어오면 pop() 해주면서 짝이 맞는지 검사하는것이다. 

이렇게 특정 조건이 stack에 쌓인 데이터를 꺼내는 역할을 하게되는 경우에 집중해야한다.

 

오늘 풀어볼 문제는 프로그래머스에 주식 가격이라는 문제이다.

input으로 주식 가격 리스트가 들어오는데, 주식이 떨어지지 않은 일자를 return 해주는 문제이다.

문제링크 > https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

예시)

• input = [1,2,3,2,3]
• output = [4,3,1,1,0] 

이 문제를 두가지 방법으로 풀어보았는데, 두가지 풀이방법과 성능을 비교해보자.

문제 풀이

1. deque

1) 사용한 자료구조와 풀이 개념

파이썬에서 제공하는 deque 패키지를 사용해서 풀이했다.

deque를 사용한 이유는 0번째 인덱스를 계속 pop해서 뒤에오는 주식 가격들과 비교해주고 싶었는데, stack을 사용할 경우 맨 왼쪽 인덱스 값을 꺼내고 싶을 때 O(N)이 걸리고, 큐를 사용하면 O(1) 이 걸리기 때문에 큐를 생각했다.

 

2) 로직 

while 주식 리스트 길이:

    맨 앞 주식 값 pop

    for 주식 리스트:

        값 비교해서 같거나 크면 +1

        작아지면 break 해서 더이상 계산하지 않도록 

 

3) 코드

from collections import deque
def solution(prices):
# 1. 큐 풀이
    cnt = 0
    deq = deque(prices)
    result = []
    while deq:
        target = deq.popleft()
        
        for i in deq:
            if target <= i:
                cnt +=1
            else:
                cnt +=1
                break
        result.append(cnt)
        cnt = 0
    return result

 

4) 효율 

1차로 prices 리스트를 전체적으로 도는데 그 안에서 또 한번 작은 값이 나올때까지 리스트를 돌기때문에 최악의 경우 O(n^)이 걸리게 된다. 그래서 아슬아슬한 코드이다. else 문에 break를 걸어주지 않으면 처음으로 떨어진 값이 나왔는데도 쓸데없이 리스트를 끝까지 돌게되고 이러면 효율성에서 통과가 안된다. 

2. stack 사용

1) 사용한 자료구조와 풀이 개념

stack을 사용해서 prices리스트를 한번만 돌면서 구현하는게 가능하다..!

이건 머리로 이해하기 굉장히 어려웠는데, 메모장에 직접 한칸 한칸 그리면서 해보길 추천한다.

아까 위에서 잠깐 얘기한 스택 단골문제인 괄호 검사 문제는 "("가 들어오면 스택에 쌓고, ")" 가 들어오면 pop을 해서 조건을 검사하게된다. 이러면 전체리스트를 한번만 돌면서 구현할 수 있게되는데, 이 개념을 적용해보자.

문제에서 주식 가격이 떨어지지 않은 일 수를 계산해달라고 했다. stack에 하나씩 push하는데, 주식 가격이 작아질 경우 stack안에 값을 꺼내게 된다. 꺼내서 떨어지기까지 얼마나 걸렸는지 계산하는데 이건 prices에 저장된 Index차이로 계산한다. 

prices = [1,3,2,1]로 주어졌을 때 stack에 쌓이는 값과 pop되는 값을 쭉 그려봤는데.. 직접 그려보길 추천한다.

2) 로직

for price 리스트 돌면서

if  stack에 값이 있고, 주식 가격이 떨어짐

  가격이 낮은 동안 pop 하면서 index 차이 계산해서 result에 넣어주기

else 

  stack에 push

+ stack에서 나가지 못한 값 처리해주기 

 

3) 코드

def solution(prices):

# 2. 스택 풀이
    stack = []
    result = [0] * len(prices)
    for i,v in enumerate(prices):
        while stack and stack[-1][1] > v:
            prev_i, prev_v = stack.pop()
            result[prev_i] = i-prev_i
        stack.append((i,v))
    for i,v in enumerate(stack):
        last_i,last_v  = stack[-1][0], stack[-1][1]
        result[stack[i][0]] = last_i - stack[i][0] 
        
    return result

4) 효율성

코드는 좀 더 복잡해보이는데 1번 O(N^)에 비해 절반정도로 시간이 줄어든 것을 확인 할 수 있다. 

주식 가격 list를 돌면서 stack 에 값이 있고, 더 적은 값이 들어오면 pop을 해주고 아닌 경우 계속 stack에 값을 push한다.

마지막에 for문을 하나 더 추가한건, prices 리스트를 한 번 다 돈 후에 끝까지 가격이 떨어진 경우를 만나지못해 stack에 남아있는 값들을 계산해주기 위함이다. 

 

 

다른 문제 참고

2023.09.06 - 프로그래머스 lv2. 기능개발 (스택/큐로 풀기)

프로그래머스 lv2. 기능개발 (스택/큐로 풀기)