[BOJ / 백준] 11899 괄호 끼워넣기 (S3^ / Stack) - Python

링크

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

 

 

 

 

문제 해석

괄호열이 주어졌을 때, 왼쪽과 오른쪽에 몇 개의 괄호를 추가함으로써 완벽한 괄호열이 되는지 구하시오.

 

 

 

입력
첫 번째 줄 : s
  s : 괄호열

출력
올바른 괄호열로 만들기 위해 앞과 뒤에 붙여야할 괄호의 최소 개수 구하기

 

 

 

 

풀이 & 코드 해석

코드 구현은 생각보다 단순합니다.

 

여는 괄호( '(' )를 만나면 stack에 push,

닫는 괄호( ')' )를 만나면 stack에 값 하나를 pop 

하면 됩니다.

 

 

 

괄호열이 "(" 인 경우
위 괄호열의 0번 인덱스 괄호는 '('입니다.
'('는 추후 ')'의 여부에 따라서 완벽환 괄호가 될 수 있습니다.
따라서 stack에 해당 값을 저장해 놓습니다.


괄호열의 괄호가 한 개 이기 때문에 마지막에 도달하였습니다.
stack을 보면 '('가 하나 존재합니다.
그말은 ')'와 매칭되지 않은 '('가 하나 존재한다는 뜻입니다.
따라서 stack의 크기만큼 ')'가 부족하다는 뜻이고, stack의 개수만큼 ')' 우측에 붙여주어야 한다는 말이 됩니다.

-> stack의 크기로 오른쪽에 붙여줄 괄호 개수를 알 수 있음

 

 

 

괄호열이 ")"인 경우
위 괄호열의 0번 인덱스에 괄호는 ')'입니다.
앞에서 '('가 있었다면 stack에 '('가 저장되어 있을 것이고, 한 개를 빼서 매칭을 시켜주면 올바른 괄호열이 되었을 것입니다.

하지만 stack이 비어있기 때문에 0번 인덱스의 괄호는 올바른 괄호열이 될 수 없습니다. 따라서 우리는 '(' 괄호열 하나가 필요하다는 의미로 변수 left에 1을 더해줍니다.

-> 변수 left는 '('가 부족한 개수를 알려줌

 

 

위 예시를 통해서 괄호열을 모두 돌았을 때 '('가 부족함을 알려주는 left 변수의 값과, ')'의 부족한 개수를 알려주는 stack의 크기를 합한 값이 우리가 필요한 괄호열의 개수가 됩니다.

 

 

 

 

코드

s = input()

left = 0
stack = []

for c in s:
    if c == '(':
        stack.append('(')
    else:
        if stack:
            stack.pop()
        else:
            left += 1

print(left + len(stack))

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java