4889 안정적인 문자열 _python

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

4889번: 안정적인 문자열

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

{} -> 올바르다. 라고 봤을때

{}{}도 올바르고 {{}}도 올바르다고 볼수있다.

하지만 }{는 틀렸고, }}{{도 틀렸다.

괄호문제는 대부분 스택으로 풀면 된다. 이문제또한 스택문제다.

스택으로 {와 }를 계산해나가면 된다.

 

처음 이문제를 접근할 때 이해를 잘못했는데 최소연산수를 구해야하면 너무 단순하게봐선 안되는 것이였다.

}}}{{{가 6으로 나오는데 4가나와야 한다. 이해가 안됐는데...

나는 {{{}}}로 바꿔야한다고 당연히 생각했으나

생각해보니 {{}{}}라고 바꾸면 4번만에 해결가능하다.

그리고 {}{}{}라고 바꾸는것도 4번만에 가능하다.

사실 이렇게 경우를 다 찾아보지 않더라도 문제를 푸는데 지장없다.

 

문제를 접근하려면 스택에 문자열이 쌓이는 경우는 }뒤에 {가 나오는경우밖에 없다.

그래서 }가나올때만 앞에 {가 있는지 체크해주면 되고

이거로 개수를 세어나가면 된다.

그리고 마지막에 left부분과 right부분의 개수를 세어주고 최소한의 연산수를 계산해주면 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

틀린 코드

from collections import deque
import sys
input = sys.stdin.readline

count = 0
while True:
    count+=1
    brace = deque(input().rstrip())
    left = 0
    right = 0
    x = brace.popleft()
    if x=="{":
        left += 1
    elif x == "}":
        right += 1
    else:
        break

    for i in range(len(brace)):
        x = brace.popleft()
        if x=="{":
            left+=1
        elif x=="}":
            if left>0:
                left-=1
            else:
                right+=1
        else:
            break
    else:
        if left>right:
            ans = (left-right)//2 + right*2
        else:
            ans = (right-left)//2 + left*2    
        print(str(count) + ". " + str(ans))
        continue
    break

}}}{{{를 입력시 6이 나온 코드

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

맞는 코드

"-"가 마지막줄에는 나온다고 했는데 괄호안에 나오는지 그냥 "-"라고만 나오는지 설명을 안해줘서 전부 체크해줬다.

from collections import deque
import sys
input = sys.stdin.readline

count = 0
while True:
    count+=1
    brace = deque(input().rstrip())
    left = 0
    right = 0
    x = brace.popleft()
    if x=="{":
        left += 1
    elif x == "}":
        right += 1
    else:
        break

    for i in range(len(brace)):
        x = brace.popleft()
        if x=="{":
            left+=1
        elif x=="}":
            if left>0:
                left-=1
            else:
                right+=1
        else:
            break
    else:
        if left%2 and right %2:
            ans = left//2 + right//2 + 2
        else:
            ans = left//2 + right//2
        print(str(count) + ". " + str(ans))
        continue
    break

104ms

 

 

다른사람 코드를 보니 더짧고 빠른코드가 많았는데... 신기했다.