[백준] 11899 파이썬(python) : 괄호 끼워넣기 - 필요한 괄호 개수 세기

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

11899번: 괄호 끼워넣기

 

 

 

 

import sys
string = sys.stdin.readline().rstrip()
stack, cnt = [], 0 #1
for char in string:
    if char == '(': #2
        stack.append(char)
    else:
        if stack and stack[-1] == '(': #3
            stack.pop()
        elif not stack: #4
            cnt += 1
cnt += len(stack) #5
print(cnt)

 

#1 : stack과 개수를 세어줄 변수 cnt 선언

#2 : 여는 괄호일때 stack에 삽입

#3 : 닫는 괄호이고 stack의 top이 여는 괄호일때 stack.pop()

#4 : 닫는 괄호이고 stack이 비어있을때 cnt +1 ( 닫는 괄호만 들어오면 안되니까 여는 괄호를 넣어줘야 해서 cnt +1)

#5 : stack에 남아있는 여는 괄호의 개수만큼 cnt에 추가

 

(()가 들어오면 맨 처음 들어오는 여는 괄호는 짝을 찾지 못하므로 닫는 괄호 한개가 필요하므로 stack에 넣어놓고 cnt에 stack의 개수만큼 추가

 

)))()가 들어오면 닫는괄호 3개는 여는 괄호 3개로 짝을 맞춰줘야 하기 때문에 cnt 3개 추가

 

))()((가 들어오면 왼쪽의 닫는 괄호 2개는 여는 괄호 2개가 필요하니 cnt 2개 추가 오른쪽의 여는 괄호 2개는 닫는 괄호 2개가 필요하니 cnt 2개 추가

 

)(()(()))는 첫번째 닫는 괄호 1개가 여는 괄호 1개 필요한것 말고는 모두 짝을 이루니 cnt 1개 추가

 

이전에 비슷한 문제를 풀어서 풀 수 있었다. 역시 최대한 많은 문제를 풀고 복기하는 방법으로 공부하는게 맞는거 같다. 더 열심히 하겠다.

 

https://hgk5722.tistory.com/259

[백준] 4889 파이썬(python) : 안정적인 문자열