[백준] 4889번: 안정적인 문자열

문제 링크: https://www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

 

맨 처음 시도 방법

import sys
input = sys.stdin.readline

flag = True
count = 1
while flag:
    a = list(input().rstrip())
    if '-' in a:
        flag = False
    res = 0
    
    # 여기서 바꿔주지 않으면, 아래 for문에서 res가 중복되어 count될 수 있음
    if a[0] != '{':
        a[0] = '{'
        res += 1

    if a[-1] != '}':
        a[-1] = '}'
        res += 1
    
    for i in range(len(a)//2):
        if a[i] == a[-(i+1)]:
            res += 1

    print(f"{count}. {res}")
    count += 1

하지만, 이 경우에는 {}{}{}{{}} <-- 이런 경우(괄호가 비대칭적으로 있는 경우)에는 대응을 하지 못한다.

 

따라서 stack을 활용해서 문제를 풀어야한다. 

1. { 를 담는 list를 만든다.

2. { 가 아닐 경우 ( }일 경우)

2-1. stack에 { 가 있으면, {를 빼준다. (짝을 맞춰 나간 것)

2-2. stack에 쌓였는 게 없으면, 짝이 맞지 않는 것이므로 res += 1을 해주고, stack에 append 한다. 

 

import sys
input = sys.stdin.readline


num = 1
while True:
    a = list(input().rstrip())
    res = 0
    if '-' in a:
        break
    stack = []
    for i in a:
        if i == '{':
            stack.append(i)
        else:
            if stack:
                stack.pop()
            else:
                res += 1
                stack.append(i)
    res += len(stack) // 2

    print(f"{num}. {res}")
    num += 1