[백준] 4889 파이썬(python) : 안정적인 문자열 - 개수 세기

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

4889번: 안정적인 문자열

 

 

이 루트를 반복하면 된다.

1. { 이면 스택에 삽입

2. } 인데 스택에 원소가 있고 stack[-1] == '{'이면 stack.pop() 수행

3. } 인데 스택이 비어있으면 stack에 { 를 삽입 (바꿔준다고 생각) 그리고 cnt +1 추가

4. stack에 들어있는건 여는 괄호 {뿐이니까 남아있다면 그것의 절반의 숫자를 cnt에 추가(절반은 닫는 괄호 }로 바꿔주는거니까)

 

import sys
ans = []
while True:
    cnt = 0 #1
    string = sys.stdin.readline().rstrip()
    stack = []

    if '-' in string: #2
        break
    for i in string:
        if i == '{': #3
            stack.append(i)
        else: #4
            if stack and stack[-1] == '{': #5
                stack.pop()
            elif not stack: #6
                cnt += 1
                stack.append('{')
    cnt += len(stack)//2 #7
    ans.append(cnt) #8
for i in range(len(ans)):
    print(f'{i+1}. {ans[i]}') #9

 

#1 : 수정할 횟수를 세어줄 변수 선언

#2 : 만일 -가 하나라도 있으면 break

#3 : 여는 괄호라면 stack에 추가

#4 : 닫는 괄호라면

#5 : 스택이 비어있지 않고 stack의 top이 여는 괄호라면 stack.pop() 실행

#6 : 닫는 괄호인데 stack이 비어있다면 여는 괄호 { 를 스택에 추가하고 cnt +1

} 를 { 로 바꿔준것이니까 횟수 추가

#7 : stack에 남아있는것은 여는 괄호 {뿐인데 만일 남아있다면 여는 괄호가 짝수개로 남아 있을테니 그 수의 절반을 닫는 괄호로 바꾼다고 생각하고 len(stack)//2를 횟수에 추가

#8 : 세어준 횟수들을 ans에 추가

#9 : 하나씩 출력 f-string 사용

 

https://hgk5722.tistory.com/250

[백준] 2504 파이썬(python) : 괄호의 값 - (★)