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

문제

 

 

 

이 문제를 처음 봤을때는 쓸 수 있을 법한 알고리즘이 쉽게 생각나지는 않았다. 그나마 생각난게 스택 또는 큐를 활용하면 될려나 하는 생각만 들었다.

 

그래서 일단 주어진 예시대로 차근차근 계산해가면서 규칙을 찾아보았다.

 

 

 

이 예시를 기준으로 생각해보자

 

앞에 시작 부분은 막대기가 주어지지 않은채 () 레이저가 왔으므로 0

 

그다음에 ((( 이렇게 막대기가 3개가 오는 것을 알 수 있다. 그리고 그 후에 () 레이저가 와서 기존에 있던 3개의 막대기를 자른 다는 것을 알 수 있다.

 

그리고 또 레이저가 와서 현재 기준 3개인 막대기를 또 자른다 그러고 ) 가 와서 이 이후에는 막대기가 두개가 된다.

 

결론은 () 이렇게 오는 레이저 말고 ((( 이런식으로 여는 괄호만 올 때 =  막대기가 시작될 때 이므로 현재 좌표 기준 막대기의 개수를 저장해주면 된다.

 

그리고 닫는 괄호가 올 때는 막대기가 끝나면서 잘린 조각중 마지막 조각을 고려하여 +1을 해주면 된다

 

 

 

정리

 

1. '(' 여는 괄호만 올 때 = 현재 막대기 개수 + 1
2. ')' 닫는 괄호만 올 때 = 현재 막대기개수 -1 해주고, 정답에 +1 (잘린 조각중 마지막 조각 +1 해주어야하므로)
3. 레이저를 만나면 현재 막대기 개수만큼 더해줌 (현재 레이저 밑에 존재하는 막대기가 잘리므로)

 

 

레이저가 나오는 좌표의 왼쪽 기준으로 계산해주고 잘린 막대기의 마지막 조각의 카운트는 닫는 괄호가 왔을 때 더해주는 거라고 생각하면 된다.

 

 

코드

 

arr = list(input())

ans = 0
#현재 막대기 개수 저장하는 변수
now_stick = 0
for i in range(len(arr)):
    if arr[i] == '(':
        if i+1 < len(arr):
            #현재가 레이저라면
            if arr[i+1] ==')':
                #현재 저장된 막대기 개수만큼 잘렸으므로 정답에 플러스
                ans += now_stick
            else:
                #막대기가 하나 더 생긴거라면 막대기 개수 플러스 1
                now_stick+= 1
                
    elif arr[i] == ')':
        if i-1 >= 0:
            #레이저가 아닌 닫는 괄호가 온거라면
            if arr[i-1] !='(':
                #지금 끝나는 막대기의 마지막 조각을 정답에 +1
                ans += 1
                #막대기가 끝났으므로 현재 막대기 개수에서 -1
                now_stick -=1
print(ans)