[스택] 쇠막대기

📌

아래에서 위로 쇠막대기를 겹쳐 놓고, 레이저를 수직으로 발사하여 쇠막대기들을 자른다.

쇠막대기와 레이저의 배치는 다음과 같다.

 

() (((() ()) (()) ())) (())

① 레이저는 인접한 쌍 '()' 으로 표현된다.

② 쇠막대기의 왼쪽 끝은 여는 괄호 '(' 이고, 오른쪽 끝은 닫힌 괄호 ')' 로 표현된다.

 

 

<input>

()(((()())(())()))(())

 

 

✔️ code

import sys
sys.stdin=open("input.txt")

arr=list(input())
bar=0   #막대기 개수
stack=[]

for i in range(len(arr)):
    if arr[i]=='(':
        stack.append(arr[i])
    else:
        stack.pop()
        if arr[i-1]=='(':
            bar+=len(stack)
        else:
            bar+=1
print(bar)

 

 

# solve:

리스트를 돌면서 만약 '(' 이면 막대기 시작점 이므로 stack 에 append() 한다.

이 시작점이 끝점 ')' 을 만날 때까지 append() 하다가 만났다면 막대기가 끝난 것이므로 pop() 한다.

도중에 레이저가 있다면 현재 stack 에 막대기가 쌓여있는 만큼 잘려진 개수가 나오므로,

bar 변수에 잘려진 개수를 더해준다.

레이저가 아닌 막대기가 끝나는 지점이라면 막대기 개수가 하나 추가되므로 bar 에 +1 을 해준다.

 

 

>>>

best code를 보니 굳이 처음에 list를 쓰고 나서 반복문을 돌지 않아도 되는 것 같다.

바로 input() 받으면 되는데 그동안 기계적으로 list() 로 묶어버렸다 보니 ... 

코드 자체는 어렵지 않았다. 주어진 그림을 보면서 단순히 레이저가 쏘면 막대기가 몇 개 늘어나지? 하면서 개수를 세다보니 알고리즘을 알 수 있었다.

운이 좋았다(?)