[Python] 25918번 북극곰은 괄호를 찢어

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

25918번: 북극곰은 괄호를 찢어

---

 

22/11/07

 

 

에디토리얼에서는 그리디 문제라고 나와있었으나, 조금 스택을 곁들인 애드 혹 스러운 문제로, 쉬운 방법으로 구현할 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

카운터 변수를 하나 선언을 해주고 괄호 문자열에서 (가 나오면 그 변수에 1을 더하고 )가 나오면 1을 뺐다.

 

북극곰은 항상 () 또는 )(처럼 열린 괄호와 닫힌 괄호를 쌍으로 생성하기 때문에, 북극곰이 생성할 수 있는 문자열이라면 저 과정을 거치면 항상 마지막에는 카운터 변수가 0이 나올 것이다.

 

때문에 이를 통해서 북극곰이 이 문자열을 생성할 수 있는지의 여부를 판별 할 수 있었다.

 

 

만약 ()()을 우리가 생성한다고 하면, O를 2개 놓거나, O를 놓은 뒤에 하루가 지나 그 사이에 X를 놓을 수 있다.

 

근데 후자는 전자보다 손해다. (이는 쉽게 알 수 있다.)

 

)()(를 만드는 경우도 마찬가지인데, 이것 또한 X를 2개 놓는 것이 더 이득이다.

 

 

결론적으로 이야기 하자면, 카운터 변수의 절댓값의 최댓값이 원하는 문자열을 만드는데에 걸리는 최소 일수와 같다.

 

예를 들어, (())는 항상 O안에 O를 넣는 것만으로 밖에 생성할 수가 없다. ))((도 비슷하게 X안에 X를 넣는 것만으로 밖에 생성할 수 없고, ((()))와 같은 문자열도 비슷하다.

 

위에서 이야기 한 것과 이를 조합을 해보자.

 

예를 들어, "()()" 만약 이런 모양이면 최소 일수는 1일이다. 그 이유는 O를 2개 놓을 수 있기 때문이다.

 

"((()))))(("이면, 최소 일수는 3일이다. 그 이유는 O와 X를 동시에 생성, 이후 만들어진 ()안에는 O를 넣고 )(안에는 X를 넣는다. 이후 만들어진 (())안에 O를 넣으면 총 3일이 걸린다.

 

다른 예시를 봐보자. "(()))((())"는 2일이 걸린다. 그 이유는 O, X, O를 동시에 생성, 이후 만들어진 ()안에는 O를 넣으면 2일이 걸리기 때문이다.

 

 

보면, 카운터 변수의 절댓값의 최댓값이 원하는 문자열을 만드는데에 걸리는 최소 일수와 같다는 사실을 알 수 있다.

 

이를 떠올리기만 한다면, 구현하는 것은 쉽게 할 수 있다.

 

근데 왜 그게 왜 최소 일수와 같냐고 하면, 스택 개념을 떠올리면 쉽게 이해할 수 있을 것이다.

 

괄호문자열 문제를 접근할 때에도 위와 같이 괄호의 종류에 따라 접근을 하는데, 이와 똑같은 접근이고, 대신에 여기는 카운터라는 변수로 스택을 모델링 했을 뿐이기 때문이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 25918번 북극곰은 괄호를 찢어
# 스택
import sys
input = sys.stdin.readline

N = int(input())
S = input().rstrip()
min_day = 0
total = 0
for char in S:
    if char == '(':
        total += 1
    else:
        total -= 1
    if abs(total) > min_day:
        min_day = abs(total)
if total == 0:
    print(min_day)
else:
    print(-1)