[Baekjoon] 백준 알고리즘: 11899 - 괄호 끼워넣기

문제

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

11899번: 괄호 끼워넣기

내가 생각했던 풀이과정

 

1. 스택을 이용해서 푸는 문제입니다. 

 

2. 괄호가 올바른지 확인을 해야합니다. 

 

1. 여는 괄호가 나오면 스택에 추가

2. 닫는 괄호가 나왔을 경우

  2-1) 스택이 비어있으면 올바르지 않은 괄호 쌍

  2-2) 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호쌍

  2-3) 스택의 top이 짝이 맞는 괄호일 경우 pop

3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아 있지 않으면 올바른 괄호 쌍

 

올바르지 않은 괄호쌍은 그대로 스택에 추가하고 올바른 괄호일 경우에만 pop을 합니다.

 

4. 올바르지 않은 괄호쌍은 그대로 스택에 남아있을테니 그 갯수를 count 해주면 됩니다.

나의 풀이

S = input()

stk = []
count = 0
for i in range(len(S)):
    if S[i] == '(':
        stk.append(S[i])
    else:
        if (len(stk) == 0 or stk[-1] != '('):
            stk.append(S[i]) # 올바르지 않은 괄호라도 stk에 넣는다
        elif S[i] == ')':
            stk.pop()
print(len(stk))

새로 알게된 점, 확인해야할 점