[백준 25918번] 북극곰은 괄호를 찢어 (Python)

> 파이썬, 자료 구조, 그리디 알고리즘, 애드 혹, 스택

 

 

 

 

 

📖 문제 : 북극곰은 괄호를 찢어 (Python)

 

 

 

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

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

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

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

 

입력

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

 N

  S

 

출력

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

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

 

제한

•  1 ≤ N ≤ 200,000
•  S는 '(' 또는 ')'로 이루어져 있다.

 

예제 입력 1 

6
()()()

 

예제 출력 1

1

 

 

 

내 코드

N = int(input())
bear = list(map(str, input()))

stack = []
result = 0

for i in range(len(bear)):
    if len(stack) == 0 or stack[-1] == bear[i]:
        stack.append(bear[i])
    else:
        if len(stack) != 0:
            stack.pop()

    result = max(result, len(stack))

if len(stack) == 0:
    print(result)
else:
    print(-1)

 

 

 

Point ! ⭐️ 

• 예제 2번을 예로 들면,

10
(()))((())

stack에 괄호에 있는 원소들을 앞에서 부터 하나씩 넣어줍니다.
이때,
() 또는 )( 이렇게 한 쌍이 만들어질 경우 이 전에 있던 (같이 쌍이 되는 것)을 빼주고, 현재 괄호도 넣지 않습니다.

현재 들어갈 요소는 )

stack = [(] 일경우 현재 들어갈 요소와 이미 들어가 있는 것과 한 쌍이 만들어지므로
넣지 않고, 그 전에꺼도 pop해주는 방식입니다. 

여기서 
최소 며칠이 걸리는지에 대한 값을 len(stack)의 맥스 값으로 한 이유는,

위의 예제에서

(()))((())일 경우, 앞에서 부터 읽어 stack에 넣는다고 하면,

stack = [((], 현재 들어갈 요소 ) (세번째 있는 요소) 이면 위의 방식대로
stack에는 stack = [(] 이렇게 남게됩니다. 왜냐하면 앞에 ( 괄호는 아직 짝을 못만났기 때문에 !

결국, stack의 길이가 문자열을 만들기 위한 최소 일수가 되는 것입니다.

 

 

 

 

백준

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

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