[PS] 북극곰은 괄호를 찢어

Byeonggwan Kang·2023년 10월 26일

목록 보기

9/10

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

문제 설명

극지 연구소에서 연구 중인 협이는 새로운 북극곰의 특성을 발견했다. 그것은 바로 북극곰이 $O$ 와 $X$ 를 보면 $()$ 와 $)($ 로 찢어버린다는 것이다.

협이는 이러한 북극곰의 특성을 이용하여 길이 $N$ 의 괄호 문자열 $S$ 를 만들고자 한다. 북극곰은 낮에 활동을 하기 때문에 낮에 돌아다니는 것은 위험하다. 때문에 협이는 매일 밤마다 활동할 수 있다. 밤에 협이는 문자열이 있으면 그 위에 $O$ 또는 $X$ 를 원하는 만큼 놓을 수 있다. 그러면 낮에 북극곰이 와서 문자들을 모두 찢어 놓는다.

예를 들어 이미 문자열 $()()$ 가 있다고 생각해보자. 밤에 문자를 $(O)X(O)$ 다음과 같이 놓아둔다면 하루가 지나 $(()))((())$ 와 같은 문자열이 된다.

이때 원하는 문자열을 만들려면 최소 며칠이 걸리는지 계산해보자.

입력

입력은 아래와 같이 주어진다.

$N$
$S$

출력

원하는 문자열을 만들기 위해 걸리는 최소 일수를 구하라.

원하는 문자열을 만들 수 없다면 -1을 출력한다.

제한

$1\leq N\leq 200\,000$

$S$ 는 '(' 또는 ')'로 이루어져 있다.

문제 해결 방법

문제 자체는 처음 보는 것 같지만 사실 완전한 괄호인지 확인하는 문제와 다를 게 없다.

사실 문제가 이게 도대체 무슨 말인지 이해하는 게 더 오래 걸렸다.

이게 몇 일이 걸릴지 세는 것은 괄호를 만드는 것이 아니라 반대로 O와 X를 만들면 몇 일이 걸릴지 생각하면 된다.

즉 문자열이 (()(())) 이라면,

1일 후, (O(O)) 이 된다.
- 만들어진 O는 제거하므로 (()) 이 된다.
2일 후, (O) 이 된다.
- () 이 된다.
3일 후, O이 된다. 끝.

대충 이런 방식이다.

즉 문자열을 차례대로 탐색하되, 스택 하나를 준비해서 현재 문자와 스택 맨 위 문자가 같은 문자라면 append하고, 아니면 pop하면 된다.

그럼 몇 일이 걸리는지는 어떻게 알까?

위 (()(()))의 예시를 잘 생각해보면, 스택 길이의 최댓값이 구하고자 하는 최소 일수라는 걸 알 수 있다.

코드 구현

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

N = map(int, input())
S = input()

answer = 0
l = []

for c in S:
    if c == '\n':
        break
    if len(l) == 0 or l[-1] == c:
        l.append(c)
    else:
        l.pop()
    answer = max(answer, len(l))
        
if len(l) == 0:
    print(answer)
else:
    print(-1)