[백준 10799][파이썬] 쇠막대기

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

10799번: 쇠막대기

https://growth-coder.tistory.com/82

 

이전에 풀었던 괄호 문제와 유사한 스택을 활용한 문제이다.

 

이 문제는 레이저를 만났을 때의 쇠막대기의 개수가 중요하다.

 

그냥 쇠막대기의 개수가 아니라 레이저를 만났을 때 관통중인 쇠막대기의 개수이다.

 

다시 말해 아직 ')' 를 만나지 못한 '(' 문자의 개수가 중요하다.

 

그렇다면 아직 ')' 를 만나지 못한 '(' 문자의 개수를 어떻게 구할 수 있을까?

 

백준 9012번 문제를 풀어보았다면 쉽게 구할 수 있다.

 

'('를 만나면 개수를 1 증가시키고 ')'를 만나면 개수를 1 감소시키면 된다.

 

문제를 푸는 알고리즘은 다음과 같다.

 

1. 아직 ')' 를 만나지 못한 '(' 문자의 개수와 현재 조각의 개수를 구분한다.

 

2. '('를 만나면 '(' 문자의 개수와 현재 조각의 개수 모두를 1씩 증가시킨다.

 

3. ')'를 만났을 때 이전 문자가 '(' 였을 경우

 

레이저를 의미하므로 현재 조각의 개수에 아직 ')' 를 만나지 못한 '(' 문자의 개수를 더한다. 

 

3. ')'를 만났을 때 이전 문자가 '(' 이 아니었을 경우

 

'(' 문자가 ')'을 만난 것을 의미하므로  아직 ')' 를 만나지 못한 '(' 문자의 개수를 1 감소시킨다.

 

<전체 코드>

import sys 
ps=sys.stdin.readline().strip('\n')
stack=0
cnt=0
for i in range(len(ps)):
    if ps[i]=='(':
        stack+=1
        cnt+=1
    elif ps[i-1]=='(':
        stack-=1
        cnt-=1
        cnt+=stack
    else:
        stack-=1

print(cnt)