Stack

스택(Stack)

스택 데이터를 임시 저장할 때 사용하는 자료구조, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식이다. 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조로 되어있다.데이터를 넣을 때는 push, 데이터를 꺼낼 때는 pop을 사용한다. 파이썬에서는 보통 스택을 구현하지 않고 리스트로 만들고 append 해서 데이터를 넣거나 pop으로 데이터를 꺼낸다.아래의 코드는 스택을 클래스로 구현해본 것이다. 코드 class Stack: class Empty(Exception): """스택이 비어있을 때 pop 또는 peek 를 수행할 때 예외 처리""" print("야") pass class Full(Exception): """스택이 가득일 때 push 를 수행할 때 예외 처리""" pass def __in..

[python] 백준 - 1874. 스택 수열

🤔문제 해결 S2 | 스택 수열 스택을 이용한 문제 스택에 값이 있고 스택의 마지막 값이 뽑아야 하는 값이면 pop 그렇지 않을 때 넣어야할 숫자가 n보다 작으면 push 둘 다 아니면 break 스택에 계속 넣는 것을 먼저 생각하는 것보다 스택에서 값을 빼는 걸 먼저 생각해야 한다. ( 연속으로 뽑을 수 있기 때문 ) 💻소스 코드 import sys input = sys.stdin.readline numbers = [] n = int(input()) for _ in range(n): numbers.append(int(input())) stack = [] result = [] number = 1 idx = 0 while idx < n: if stack and stack[-1] == numbers[idx]..

[python] 백준 - 2504. 괄호의 값

🤔문제 해결 S2 | 스택, 자료구조, 구현, 재귀 괄호문제는 항상 스택으로 풀었다. 먼저 올바른 괄호인지 체크하자! 그 다음 스택을 이용해 괄호 짝을 맞추면서 ()일 때 2, []일 때 3을 계산해준다. 만약 스택의 마지막에 숫자가 있다면 곱해준다. 만약 스택에 숫자가 연속으로 나열되면 더해준다. 💻소스 코드 def is_right(s): stack = [] for ss in s: if ss == '(': stack.append(ss) elif ss == ')': if stack and stack[-1] == '(': stack.pop() else: return False elif ss == '[': stack.append(ss) elif ss == ']': if stack and stack[-1] =..

[python] 백준 - 13335. 트럭

🤔문제 해결 S1 | 스택 대기중인 트럭, 다리위의 트럭, 다리위의 트럭의 진입 시간 을 각각의 리스트로 구성한다. 다리 위의 트럭 중 가장 앞쪽의 트럭의 진입 시간 + 다리의 길이 가 현재시간과 같으면 그 트럭을 빼준다. (도착) 다리 위의 트럭 무게의 합 + 대기 중인 트럭 중 가장 앞쪽의 트럭 무게 가 다리의 하중보다 작으면 그 트럭을 대기중인 트럭에서 빼서 다리위의 트럭으로 넣어준다. (출발) 💨 💻소스 코드 from collections import deque def solution(n, w, L, trucks): trucks = deque(trucks) # 대기중인 트럭 on_the_bridge = deque() # 다리위의 트럭 departure_time_truck = deque() # 각 ..

[python] 백준 - 10799. 쇠막대기

문제 해결 1. 스택을 활용한 문제. S3 2. '(' 가 나오면 막대기의 시작점이라 생각하고 stack 에 쌓는다. 3. ')' 이 나왔을 때 두가지의 경우 (1) 이전에 '(' 가 나온 경우: 쇠막대기가 아니라 레이저 이므로 잘라준다. (2) 이전에 ')' 가 나온 경우: 쇠막대기의 끝 부분 이다. 4. 레이저로 자른경우는 stack 에 쌓여있는 막대기만큼 count를 더해준다. 5. 쇠막대기의 끝부분이 나온경우 막대히 하나만큼 count를 더해준다. 🚗 소스 코드 bars = input() stack = [] cnt = 0 # '('를 막대기의 시작점으로 주고 '()' 이렇게 여는괄호와 닫는괄호가 연속으로 나오면 레이저로 취급한다. for i in range(len(bars)): if bars[i]..