여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.
아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.
위 예의 괄호 표현은 그림 위에 주어져 있다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 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)