[백준 4889] 안정적인 문자열 (Python)

www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

 

문제풀이

stack을 이용해 안정적이지 않은 경우 ans를 증가하는 방식으로 해결할 수 있다. 

 

1. 현재 문자가 '{' 이면 stack에 append하기

 

2. 현재 문자가 '}' 이면 stack 에서 pop하기

- stack 이 비어있을 경우 안정적이지 않은 경우이므로 ans 증가

- 이 경우 안정적이지 않은 '}' 를 바꿔줘야 하므로 '{'를 stack에 append

 

3. stack 이 남아있을 경우, stack에 남아있는 개수가 2의 배수일 경우 ans 증가하기 => 2의 배수일 경우 '{' 를 '}'로 바꿔서 안정적인 문자로 만들어야 하기 때문

 

코드

import sys

if __name__ == '__main__':
    idx = 1
    while True:
        S = list(map(str, sys.stdin.readline().rstrip()))
        if '-' in S: break
        stack = []
        ans = 0
        for y in S:
            if y == '{':
                stack.append(y)
            else:
                if stack:
                    stack.pop()
                else:
                    ans += 1
                    stack.append('{')
        while stack:
            if len(stack) % 2 == 0:
                ans += 1
            stack.pop()
        print(f'{idx}. {ans}')
        idx += 1

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!