- Date : 2021.05.23(일)
- Time : 20분
- 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.
1. 빈 문자열은 안정적이다.
2. S가 안정적이라면, {S}도 안정적인 문자열이다.
3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.
- {}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다. 문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.
- 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다. 입력의 마지막 줄은 '-'가 한 개 이상 주어진다.
- 각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.
while True:
stack = []
count = 0
s = sys.stdin.readline()
if '-' in s:
break
for i in range(len(s)):
if not stack and s[i] == '}':
count += 1
stack.append('{')
elif stack and s[i] == '}':
stack.pop()
else:
stack.append(s[i])
count += len(stack)//2
result.append(count)
: 얼마전에 푼 프로그래머스의 올바른 괄호, 괄호 회전하기
와 비슷한 문제이다! 먼저 문자열을 한줄 씩 입력받고 검사를 진행한다. 만약 stack에 아무것도 없고 여는 괄호가 나와야지 스택에 넣을 수 있다. 시작이기 때문이다. 하지만 스택에 아무것도 없는데 닫는 괄호라면 시작부터 잘못되었기 때문에 문자열을 안정적으로 바꿔줘야한다. 그리고 스택에 값이 있는데(= 여는 괄호가 존재한다는 말) 지금 문자가 닫는 괄호라면 안정적이기 때문에 stack에서 여는 괄호를 빼준다. 괄호가 완성되었기 때문이다. 이렇게 count를 더해가면 된다.