내가 보려고 만든 Python의 stack 활용법

자료구조 중 하나인 stack에 대해 알아보겠습니다. python에서 구현하였으며 c++ 도 나중에 기회되면 추가할 예정이고 풀다가 생각보다 금방 생각이 안 났거나 못 풀었던 문제, 좋은 문제를 위주로 예시를 기록해두려합니다. (본인 공부 및 기록용) 😁

stack 이란?

LIFO(Last In First Out) 형식으로 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 자료 구조입니다. 보통 python에서는 list.pop(), list.append()로 구현됩니다.

출처

예시 문제 1. 히스토그램에서 가장 큰 직사각형

백준 6549

def solution(histogram):
    histogram = histogram[1:]
    histogram.append(0)  # 끝에 높이 0을 추가하여 남은 모든 막대를 처리
    stack = [] # 스택 자료구조 이용
    max_area = 0 # 넓이

    for i in range(len(histogram)):
        while stack and histogram[stack[-1]] > histogram[i]: # 앞에 나왔던 직사각형들 중에 지금 보고 있는 직사각형보다 큰 애들 기준으로
            height = histogram[stack.pop()] # 높이와 (작은 놈이 직사각형 형성함)
            width = i if not stack else i - stack[-1] - 1 # 가로 길이를 측정하여
            max_area = max(max_area, height * width) # 넓이 최대치 구하기
        stack.append(i)

    return max_area


while True:
    arr = list(map(int, input().split()))
    if len(arr) == 1: # 0 하나만 나오면 끝!
        break

    print(solution(arr))

예시 문제 2. 크게 만들기

백준 2812

예시 문제 3. 문자열 폭발

백준 9935

array = input()
boom = input()

string_stack = []
n, m = len(array), len(boom)

for i in range(n):
    string_stack.append(array[i])

    if string_stack[-1] == boom[-1] and len(string_stack) >= m and ''.join(string_stack[-m:]) == boom:
        for _ in range(m):
            string_stack.pop()

print(''.join(string_stack)) if len(string_stack) != 0 else print("FRULA")

"""
# 엄청 큰 string_stack에서 작동한다 가정했을 때 시간복잡도가 높음
string_stack = ""
n, m = len(array), len(boom)

for i in range(n):
    string_stack = string_stack + array[i]

    if string_stack[-1] == boom[-1] and len(string_stack) >= m and string_stack[-m:] == boom:
        string_stack = string_stack[:-m] # 엄청 큰 string_stack에서 작동한다 가정했을 때 시간복잡도가 높음

print(string_stack) if len(string_stack) != 0 else print("FRULA")
"""

예시 문제 4. 오아시스 재결합

백준 3015

궁금한 것들이나 추가 및 수정했으면 좋겠는 거 말해주시면 좋을 거 같아요. 좋은 하루 보내시길 바래요 :)