[BOJ] 10799 : 쇠막대기 [자료구조](Python)

문제 링크

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

10799번: 쇠막대기

소스 코드

question = input()
stack = []
answer = 0

for idx in range(len(question)):
    if question[idx] == '(': # 열린 괄호는 추가
        stack.append('(')
    else: # 닫는 괄호의 경우
        stack.pop()
        if question[idx-1] == '(': # 레이저인 경우
            answer += len(stack)
        else: answer += 1 # 막대의 끝인 경우

print(answer)

 

해설

• 스택 자료 구조
• 단순 구현

아주 단순한 괄호 문제입니다.

우선 열린 괄호가 나타나면 스택에 추가합니다.

 

닫힌 괄호가 나타났을 땐 스택의 열린 괄호와 쌍을 이루게 되므로 스택.pop을 실행하고 두 가지 케이스로 구분합니다.

1) 레이저인 경우

닫힌 괄호의 직전 문자열이 열린 괄호인 경우 레이저를 의미합니다.

따라서 스택에 남아있는 열린 괄호의 개수만큼 정답을 더해줍니다.

스택에 남아있는 괄호의 개수가 곧 남은 막대의 개수이기 때문에 그만큼 개수가 늘어나게 되는 것입니다.

 

2) 막대의 끝인 경우

닫힌 괄호의 직전 문자열이 닫힌 괄호인 경우는 레이저가 아니라 막대기의 끝을 의미하게 됩니다.

이때는 레이저에 의해 짤리고 남은 막대기의 끝이 되므로 막대기는 한 개만 추가됩니다.

즉, 다른 막대기에는 영향을 주지 못하므로 그 자신만 추가된다는 뜻입니다.