Stack

나중에 들어온 자료가 가장 먼저 처리되는 LIFO(Last In First Out) 자료구조. 파이썬에서는 따로 자료구조를 제공하지 않고 기본 자료형인 list를 사용하여 구현할 수 있다.

Stack 사용하기

초기화

stack = []

데이터 삽입하기 : append()

시간복잡도 : O(1)

stack.append(3)

데이터 제거하기 : pop()

시간복잡도 : O(1)
가장 마지막 원소가 제거되는 메서드. 만약 특정 인덱스에 있는 값을 리턴하고 싶으면 메서드에 매개변수로 넘겨주면 된다. (이 경우에는 시간복잡도 O(N))

이 메서드는 pop된 아이템을 리턴한다.

data = stack.pop()

데이터 길이 체크 : len()

시간복잡도 : O(1)

print(len(stack))

데이터 슬라이싱 : [b:a]

시간복잡도 : O(b-a)

print(stack[1:2])

큐

먼저 들어온 자료가 가장 먼저 나가는 FIFO(First In First Out) 자료구조. 리스트의 pop(0) 메서드를 통해서도 사용할 수 있으나 시간복잡도 때문에 deque라는 자료구조를 사용한다.

Deque

양방향 큐(Double-ended Queue)로 양 끝에서 데이터의 추가/삭제가 가능한 자료구조. 내부적으로 double-linked list로 구현되어 있다.

Deque 사용하기

먼저 import를 해줘야 한다.

from collections import deque
q = deque()

데이터 삽입하기 : append(), appendleft()

시간복잡도 : O(1)
append() : 큐의 맨 뒤에 삽입
appendleft() : 큐의 맨 앞에 삽입

q.append(3)
q.appendleft(4)

데이터 제거하기 : pop() , popleft()

시간복잡도 : O(1)
pop() : 큐의 가장 마지막 원소가 제거
popleft() : 큐의 가장 첫번째 원소가 제거
만약 pop할 데이터가 없으면 IndexError 발생

이 메서드는 pop된 아이템을 리턴한다.

data = q.pop()
data = q.popleft()

프로그래머스 고득점 kit

Lv 1. 같은 숫자는 싫어

stack에 넣어주면서 가장 마지막 요소와 동일한 경우 넣지 않으면 된다.

def solution(arr):
    stack = []
    for num in arr:
        if len(stack) == 0:
            stack.append(num)
        else:
            if stack[-1] != num:
                stack.append(num)
    return stack

Lv 2. 기능개발

큐의 길이를 체크해주면서 데이터를 뽑아내면 된다. pop하고 완료될때까지 쭉 계산하며 만약 뽑을게 있다면 계속 pop해준다.

from collections import deque
import math

def solution(progresses, speeds):
    answer = []
    q = deque(progresses)
    speed_q = deque(speeds)
    
    while q:
        count = 1
        progress = q.popleft()
        speed = speed_q.popleft()
        date = math.ceil( (100-progress) / speed )
        
        if len(q) == 0:
            answer.append(count)
            break
        
        for i in range(len(q)):
            q[i] += (speed_q[i] * date)
        
        while len(q) > 0 and q[0] >= 100:
            q.popleft()
            speed_q.popleft()
            count += 1
        
        answer.append(count)
        
    return answer

Lv 2. 올바른 괄호

리스트에 (가 있어야 )를 뽑을 수 있다는 것에 초점을 맞춰서 풀었다. left 변수에 여는 괄호( 수를 체크하면서 계산. 만약 뽑을 수 없는데 뽑으려고 하면 바로 False를 리턴했다.
모든 연산이 끝나고 여는 괄호( 가 만약 남아있는 경우도 올바른 괄호가 아니므로 False 리턴하기

def solution(s):
    answer = True
    left = 0
    for item in s:
        if item == "(":
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                return False
    if left > 0:
        return False
    else:
        return True

Lv 2. 프로세스

큐에서 꺼내서 우선순위 더 높은(숫자가 더 큰) 요소가 있으면 다시 큐에 넣었다. 뽑은 요소가 언제 실행되는지 체크해야 하므로 큐를 2개 사용했다.
q는 우선순위를 저장하고 order는 location(index)을 저장했다.

from collections import deque 
def solution(priorities, location):
    answer = 0
    q = deque([])
    order = deque([])
    
    
    for i in range(len(priorities)):
        q.append(priorities[i])
        order.append(i)
    
    i = 1
    while q:
        max_p = max(q)
        
        p = q.popleft()
        o = order.popleft()
        
        if p == max_p:
            if o == location:
                answer = i
            i += 1
            
        else:
            q.append(p)
            order.append(o)
        
    return answer

Lv 2. 다리를 지나는 트럭

문제에 설명이 부족하여 헤맸다. 포인트는 트럭이 다리를 통과하려면 bridge_length만큼 지나가야 한다는 것! 따라서 트럭이 얼마만큼 통과하였는지를 세어서 차례차례 지나가야함

from collections import deque


def solution(bridge_length, weight, truck_weights):
    bridge = deque([])  # 다리에 올라간 트럭 무게
    trucks = deque(truck_weights)
    bridge_count = deque([])
    time = 0

    while True:
        time += 1
        if len(bridge) != 0:  # 1초가 지났으니 다리에 올라간 트럭들이 이동
            for i in range(len(bridge)):
                bridge_count[i] += 1

        # 나갈 트럭은 나가기
        while len(bridge) != 0 and bridge_count[0] > bridge_length:
            bridge.popleft()
            bridge_count.popleft()
        if (
            len(trucks) != 0
            and trucks[0] + sum(bridge) <= weight
            and len(bridge) + 1 <= bridge_length
        ):
            bridge.append(trucks[0])
            bridge_count.append(1)
            trucks.popleft()

        if len(trucks) == 0 and len(bridge) == 0:
            break
    return time

Lv 2. 주식가격

Stack으로 풀었다. 주식 가격이 상승할때만 오름차순으로 stack에 넣어주었고 주식이 떨어지면 본인보다 큰 값은 다 스택에서 제거하기.

stack에는 (가격, 순서)로 넣었다.

def solution(prices):
    answer = [0] * len(prices)
    increase = []
    for i in range(len(prices)):
        if len(increase) == 0:
            increase.append([prices[i], i])  # 가격, 순서
            continue
        if increase[-1][0] <= prices[i]:  # 주식가격 상승
            increase.append([prices[i], i])  # 가격, 순서
        else:  # 가격 하락
            while len(increase) != 0 and increase[-1][0] > prices[i]:
                data = increase.pop()
                answer[data[1]] = i - data[1]
            increase.append([prices[i], i])  # 가격, 순서

    while len(increase) != 0:
        data = increase.pop()
        answer[data[1]] = len(prices) - 1 - data[1]  # 끝까지 안 떨어진 것
    return answer