[백준] 10799번 : 쇠막대기 - 파이썬

10799번: 쇠막대기

아이디어 : 스택

ChatGPT : 스택 알고리즘

스택(Stack)은 후입선출(Last In, First Out, LIFO)의 자료구조로, 데이터를 넣고(push) 빼내는(pop) 동작을 지원합니다. 스택은 쌓아올린 책처럼 위에서부터 차곡차곡 쌓아 올리는 구조를 가지고 있습니다.

스택 알고리즘은 스택을 활용하여 문제를 해결하는 알고리즘입니다. 스택을 이용하면 반복문이나 재귀함수 등에서 현재 처리 중인 데이터의 상태를 저장하고 나중에 다시 불러와 처리할 수 있습니다.

스택 알고리즘은 다양한 분야에서 활용됩니다. 예를 들어, 컴퓨터 과학에서는 함수 호출 시 함수 호출 정보를 스택에 저장하고, 그 함수가 끝나면 스택에서 정보를 꺼내서 호출한 곳으로 돌아갑니다. 또한, 미로찾기, 수식 계산 등에서도 스택 알고리즘이 사용됩니다.

스택 알고리즘에서 기본적으로 제공하는 연산은 다음과 같습니다.
push: 스택에 데이터를 추가합니다.
pop: 스택의 맨 위에 있는 데이터를 꺼냅니다.
top: 스택의 맨 위에 있는 데이터를 조회합니다.
empty: 스택이 비어있는지 확인합니다.

스택 알고리즘은 구현하기 간단하면서도 다양한 문제 해결에 활용됩니다.

문제 해결 과정

- ( : 쇠막대기 증가

- () : 레이저

- ) : 쇠막대기 감소

- * 고려사항 : ) 일 경우, 레이저 또는 쇠막대기 감소 *

 

스택 자료구조에 ( 를 쌓는다.

)를 만나는 경우, 레이저 또는 쇠막대기 끝인 경우인데

is_possible_raiser 변수로 직전 값이 ( 인지 상태를 저장하여, 레이저 또는 쇠막대기 끝인 경우를 구분한다.

 

따라서, 최종 stack의 사이즈는 쌓인 쇠막대 개수이며,

레이저일 경우, total =+ 쇠막대기 개수

쇠막대기일 경우, total =+ 1 을 한다.

 나의 답안

import sys

input = sys.stdin.readline
bars = input().strip()

stack = []
total = 0
is_possible_raiser = False

for bar in bars:
    if bar == '(':
        stack.append(bar)
        is_possible_raiser = True
    else:
        # raiser
        if is_possible_raiser:
            stack.pop()
            total = total + len(stack)
        # stick end
        else:
            stack.pop()
            total = total + 1
        is_possible_raiser = False

print(total)

 

추가 

파이썬 스택의 자료구조는 [] 리스트를 사용할 수 있다.

메소드는 append(), pop()

리스트의 사이즈는 len() 으로 알 수 있다.

리스트의 마지막 요소 조회는 [-1] 으로 알 수 있다.

 

https://www.acmicpc.net/problem/10799

10799번: 쇠막대기