백준 4889 안정적인 문자열

www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

cnt = 0
while True:
    ans = 0
    A = []
    s = input()
    if s.startswith('-'):
        break
        
    for i in s:
        if i == '{':
            A.append(i)
        else:
            if A:
                A.pop()
            else:
                A.append('{')
                ans+=1

    ans+= len(A) // 2 if len(A) > 1 else len(A)
    cnt+=1
    print(f'{cnt}. {ans}')

 

스택을 이용해 푸는 문제다.

1. 우선 이 문제는 무조건 쌍으로 들어오니 쌍이 안맞는 경우에 대해선 고려할 필요 없다.

2. 열린 괄호인 경우 스택에 담아준다.

3. 닫힌 괄호인 경우 스택에 요소가 있으면 스택에서 제거해준다. 정상적으로 열리고 닫힌 경우이니 스택에서 제거 해줌으로써 닫을게 남지 않은 경우

4. 열린게 없는데 닫힌 괄호가 나온 경우, 닫힌 괄호를 열린 괄호로 변경하여 스택에 넣어주고, 변경작업을 했으므로 결과값에 1 더한다

5. 입력으로 받은 모든 괄호를 순회한후, 스택이 비어있지 않은 경우, 

스택에는 열린 괄호만 담겨있기 때문에 2개 이상이라면 절반을 닫는 괄호로 변경해주면 되므로 결과에 스택 요소의 반을 더한다.

 

스택만 떠올렸다면 쉬운문제