[백준 11899] 괄호 끼워넣기

문제

올바른 괄호열은 각각의 괄호의 짝이 맞는다. 이때 올바르지 않은 괄호열이 주어졌을 때 올바른 괄호열을 만들기위해 괄호를 추가하기 위해 최소 몇 개가 필요한지 구하라.

 

입력

첫 번째 줄에 올바르지 않은 괄호열 S가 주어집니다. S의 길이는 1 이상 50 이하입니다.

 

출력

첫 번째 줄에 S를 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 출력합니다. 불가능한 경우는 주어지지 않습니다.

---

접근

스택에 이전의 괄호에 대해 기록한다. 이를 활용해서 올바르게 짝지어진 괄호들은 스택에서 pop하면 마지막엔 올바르지 않은 괄호만 스택에 남게된다.

 

구현

- 입력받은 문자열을 탐색한다.

- 여는 괄호가 나왔을 때는 스택에 push한다.

- 닫는 괄호가 나왔을 때 스택의 top이 여는 괄호라면 pop하고

- 스택이 비어있거나 스택의 top이 닫는 괄호라면 닫는 괄호를 push한다.

- 탐색이 종료되면 스택의 길이를 출력한다.

for s in S:
    if s == '(':
        stack.append(s)
    else:
        if stack and stack[-1] == '(':
            stack.pop()
        else:
            stack.append(s)

---

전체 코드

import sys
input = sys.stdin.readline

S = input().strip()
stack = []

for s in S:
    if s == '(':
        stack.append(s)
    else:
        if stack and stack[-1] == '(':
            stack.pop()
        else:
            stack.append(s)

print(len(stack))