[파이썬] BOJ 10799번 - 쇠막대기

링크

10799번: 쇠막대기

문제

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.

1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

입력

한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.

출력

잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.

풀이

• 위의 그림을 가지고 생각해보자.

• 이 문제는 스택을 가지고 풀 수 있는 문제이다.

• () 는 레이저를 뜻하고, ( 와 ) 는 분리 되어있으므로 막대기를 뜻한다고 보면 된다. 괄호가 연속으로 3개 열리면, 막대기가 3층 높이로 쌓이는 것이고, 그 뒤 레이저로 자르게 되면 잘려진 막대기는 3개가 생기는 것이다.

• 그 원리를 이용해 레이저가 나오기 전까지 열려있는 괄호가 몇 개인지를 가지고 잘려진 막대기 개수를 구해볼 수 있다.

• 그리고 레이저가 나타나고 그 뒤에 닫힌 괄호가 있다면(긴 막대기가 레이저보다 뒤에 존재하는 것) 레이저로 막대기를 잘랐을 때 잘라진 막대기가 1개 더 나올 수 있다는 것이다.
  즉 레이저가 나오고 그 뒤에 닫힌 괄호가 있다면 잘려진 막대기 개수가 +1 개 된다는 것을 알 수 있다.

• 스택에다가 괄호를 넣었다가 뺐다 하면서 위의 논리대로 개수를 구하면 된다.

• 이걸 그림으로 살펴보면 아래와 같다. 아래 그림은 문제에서 예시로 나온 괄호 set을 표현한 것이다.

• num은 괄호의 순서
• ptr은 앞에 열린 괄호가 몇개인지를 나타내는 것이다.(열린 괄호가 나오면 +1, 닫힌 괄호가 나오면 그때는 -1해준다.)
• ans는 답을 담는 수로서 레이저가 나와서 막대기를 잘라야 할 때 잘라지는 막대기의 수를 누적해서 더한 합이다.

순서

(번호는 num)
1. 괄호가 열리면 ptr을 +1 해준다. 스택에 쌓는다. 막대기가 앞으로 나올거라고 선언하는 것과 유사하다.
2. 괄호가 또 열렸으니 ptr +1. 스택에 쌓는다.
3. 괄호가 또 열렸으니 ptr +1. 스택에 쌓는다.
4. 괄호가 또 열렸으니 ptr +1. 스택에 쌓는다.
5. 닫는 괄호이니 ptr -1. 닫는 괄호가 바로 나왔으니 이건 레이저라고 판단. 레이저이면 스택의 top을 pop. 레이저로 절단해야 하니 레이저 앞에 나온 여는 괄호의 개수(ptr)만큼 ans에 더한다.(+3).
6. 괄호가 열렸으니 ptr +1. 스택에 쌓는다.
7. 닫는 괄호이니 ptr -1. 닫는 괄호가 바로 나왔으니 이건 레이저라고 판단. 스택의 top을 pop해서 레이저를 없애준다. 레이저로 절단해야 하니 레이저 앞에 나온 여는 괄호의 개수(ptr)만큼 ans에 더한다.(+3).
8. 닫는 괄호이니 ptr -1. 레이저 뒤에 나온 괄호인데 여기서 닫힌 괄호는 3의 괄호이다. 그러니 잘라진 막대기라고 볼 수 있다. ans에 +1 해준다. 3은 닫혔으니 이제 열린 괄호는 2개이다.
9. 괄호가 열렸으니 ptr +1. 스택에 쌓는다. 열린 괄호는 다시 3개가 된다.
10. 괄호가 열렸으니 ptr +1. 스택에 쌓는다.
11. 닫는 괄호이니 ptr -1. 이건 레이저라고 판단. 스택의 top을 pop해서 레이저를 없애준다.
레이저로 절단해야 하니 레이저 앞에 나온 여는 괄호의 개수(ptr)만큼 ans에 더한다.(+3).
12. 닫는 괄호이니 ptr -1. 레이저 뒤에 나온 괄호인데 여기서 닫힌 괄호는 9의 괄호이다. ans에 +1 해준다. 9는 닫혔으니 이제 열린 괄호는 2개이다.
13. 괄호가 열렸으니 ptr +1. 스택에 쌓는다.
14. 닫는 괄호이니 ptr -1. 이건 레이저라고 판단. 스택의 top을 pop해서 레이저를 없애준다.
레이저로 절단해야 하니 레이저 앞에 나온 여는 괄호의 개수(ptr)만큼 ans에 더한다.(+2).
15. 닫는 괄호이니 ptr -1. 레이저 뒤에 나온 괄호인데 여기서 닫힌 괄호는 2의 괄호이다. ans에 +1 해준다. 2는 닫혔으니 이제 열린 괄호는 1개이다.
16. 닫는 괄호이니 ptr -1. 레이저 뒤에 나온 괄호인데 여기서 닫힌 괄호는 1의 괄호이다. ans에 +1 해준다. 1는 닫혔으니 이제 열린 괄호는 0개이다.

이렇게 구하면 잘라진 막대기 개수는 15개가 나온다.

문제의 포인트

• 앞에 누적된 괄호의 개수를 파악해서 레이저가 나오는 시점에 그 괄호들을 어떻게 계산할지를 알아야 하는 것
• 잘라지는 막대기 개수와 여는 괄호 & 닫는 괄호의 개수를 어떻게 연관시킬지 파악하는 것(레이저는 제외)

코드

import sys
paren_lst = list(sys.stdin.readline().strip())
stack = []
pre = ''
pair = {')': '('}
ptr = 0
ans = 0
for par in paren_lst:
    if par in '(':
        stack.append(par)
        # 여는 괄호가 중첩될 때마다 해당 괄호가 닫힐 때 더해질 값을 미리 더함
        ptr+=1
    elif stack:
        if par == ')':
            ptr-=1
        if stack[-1] == pair[par]: 
        # par이 닫는 괄호일 때, 스택의 top이 여는 괄호이면(레이저)
            stack.pop()
            # 이전의 문자열이 현재 닫는 괄호와 쌍을 이루는 여는 괄호 인 경우에만 값을 추가
            if pre == pair[par]: #닫는 괄호가 들어왔을 때 pre가 여는 괄호이면
                ans += ptr
            else:
                ans += 1
    # 괄호가 닫힐 때 현재 값을 저장할 지 판단하기 위해 직전 문자를 저장
    pre = par
print(ans)