📘📗 스택/큐 (같은 숫자는 싫어 ~ 주식가격)

프로그래머스

• 이번에는 알고리즘 문제에 자주 등장하는 '스택 / 큐' 자료 구조를 이용한 문제들을 풀어보겠습니다!

 

스택은 뭐고 큐는 뭐죠?

• 우선 스택은 LIFO(Last-In, First-Out) 원칙을 따르는 선형 자료 구조입니다. 가장 마지막에 추가된 요소가 가장 먼저 빠져나온다는 것을 의미합니다.
• 스택은 재귀나 괄호 매칭 등의 문제에서 주로 적용되는 자료 구조입니다.
• 두 번째로 큐는 FIFO(First-In, First-Out) 원칙을 따르는 선형 구조입니다. 대기열을 관리하거나 BFS 문제에 주로 사용됩니다.
• 큐는 앞과 뒤 모두 접근이 가능하지만, 스택은 상단 요소에만 접근이 가능합니다.
• 이러한 특성들을 잘 기억해두셔서 아래 문제들에 적용하면 쉽게 풀 수 있을 것 같습니다!

 

 Level 1 : 같은 숫자는 싫어 

• 배열에서 연속적으로 중복되는 요소를 제거하여 다시금 배열을 반환하는 문제입니다.
• 스택의 원리를 이용하여 가장 마지막에 들어간 요소가 지금 추가할 요소와 중복이 되지 않는다면, 요소를 추가하는 방식으로 진행하였습니다.

def solution(arr):
    stack = []
    for e in arr:
        if not stack or stack[-1] != e:
            stack.append(e)
    return stack

 

 Level 2 : 기능 개발 

• 배포 가능한 기능이 몇 개씩 묶일 수 있는지를 계산하는 문제입니다.
• 먼저, 각 작업에 대해 남은 작업 일수를 계산하기 위해서 math 모듈의 ceil() 함수를 사용하였습니다. 이유는 전에 작성하였던 Class 2 (달팽이는 올라가고 싶다 ~ 영화감독 숌) 포스팅에서의 '2869번: 달팽이는 올라가고 싶다' 문제와 유사하니 참고하시길 바랍니다.
•  첫 번째 기능이 완료되는 날을 설정한 후, 그 날이나 그 이후에 완료되는 기능들을 같은 배포 그룹으로 묶습니다.
• 더 이상 현재 배포 그룹에 속하지 않는 작업이 나오면 현재 그룹의 count를 answer 리스트에 추가한 뒤, 새로운 배포 그룹을 생성하기 시작합니다.
• 이 풀이에서는 첫 번째 기능이 완료되는 날을 기준으로 삼고, 해당 작업이 끝나면 큐의 다음 요소를 확인하는 식으로 큐의 특징을 사용하였습니다.

import math

def solution(progresses, speeds):
    days_off = [math.ceil((100 - progress) / speed) for progress, speed in zip(progresses, speeds)]
    
    answer = []
    cnt = 1
    first_day = days_off[0]

    for day in days_off[1:]:
        if day <= first_day:
            cnt += 1
        else:
            answer.append(cnt)
            cnt = 1
            first_day = day

    answer.append(cnt)
    
    return answer

 

 Level 2 : 올바른 괄호 

• 올바른 괄호들을 구분하는 문제입니다.
• 이 문제도 스택 구조를 활용하여 열린 괄호 '('가 나올 때만 스택에 push하고, 닫힌 괄호 ')'가 나올 때는 스택에서 pop을 실행하여 올바른 괄호를 추출하도록 풀이하였습니다.

def solution(s):
    pars = []

    for char in s:
        if char == '(':
            pars.append(char)
        elif not pars:
            return False
        else:
            pars.pop()

    return not pars

 

 Level 2 : 프로세스 

• 이 문제는 실제로도 프린터나 CPU의 작업 관리 같은 시스템 설계에서 접할 수 있는 문제입니다.
• 문제에 우선순위가 주어져있긴 하지만, 우선순위 큐로 접근하는 것이 아닌 일반 큐를 우선순위에 따라 재배치하는 로직으로 풀어내셔야 합니다.
• 운영체제는 매 순간마다 가장 높은 우선순위를 가지는 프로세스를 실행시킵니다. 만약 대기 중인 프로세스 중에서 우선순위가 더 높은 것이 존재한다면, 현재 프로세스는 다시 큐에 들어가게 됩니다.

def solution(priorities, location):
    queue = [(p, idx) for idx, p in enumerate(priorities)]
    answer = 0

    while queue:
        current = queue.pop(0)
        if any(current[0] < other[0] for other in queue):
            queue.append(current)
        else:
            answer += 1
            if current[1] == location:
                break

    return answer

 

 Level 2 : 다리를 지나는 트럭 

• 각 트럭이 순차적으로 다리를 건널 때 걸리는 전체 최소 시간을 계산하는 문제입니다.
• 이번에는 파이썬에서 큐를 활용할 수 있는 방법 중 하나인 deque 라이브러리를 이용하여 구현하였습니다. deque 자료구조는 양방향 큐로, 양쪽 끝에서 요소를 빠르게 추가하거나 제거할 수 있기 때문에 시간 복잡도 면에서 큰 효율을 보여준답니다!
• 대기 중인 트럭이 있거나 다리 위에 트럭이 있는 동안 반복문을 실행시킵니다.
• 대기 중인 트럭이 있고, 다리 위의 현재 무게와 대기 중인 첫 번째 트럭의 무게 합이 다리의 최대 무게를 초과하지 않을 경우에 해당 트럭을 다리에 진입시킵니다.
• 위와 같은 상황으로 반복해주며 시간을 누적시켜주어 총 시간을 반환하는 로직입니다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0
    bridge = deque([0] * bridge_length)
    bridge_weight = 0
    truck_weights = deque(truck_weights)

    while truck_weights or bridge_weight > 0:
        time += 1
        bridge_weight -= bridge.popleft()

        if truck_weights and bridge_weight + truck_weights[0] <= weight:
            truck = truck_weights.popleft()
            bridge.append(truck)
            bridge_weight += truck
        else:
            bridge.append(0)

    return time

 

 Level 2 : 주식가격 

• 각 시점에서의 주식 가격에 대해 떨어지지 않는 시간을 계산하는 문제입니다.
• 먼저 결과 리스트를 각 가격이 떨어지지 않은 최대 기간으로 일단 초기화해둡니다.
• 빈 스택을 초기화해서 스택의 마지막 요소가 현재 가격보다 높은 경우에 스택에서 pop()를 실행해줍니다.
• 결과적으로 스택에서 나온 값을 결과 리스트에 넣어주고, 이를 prices 리스트의 길이만큼 반복해줍니다.

def solution(prices):
    length = len(prices)
    answer = [length-i-1 for i in range(length)]
    stack = []
    
    for idx in range(length):
        while stack and prices[stack[-1]] > prices[idx]:
            sec = stack.pop()
            answer[sec] = idx - sec
        stack.append(idx)

    return answer