백준 10799 - 쇠막대기

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

10799번: 쇠막대기

 

 

 

 

이 문제는, 스택을 활용하는 대표적인 문제이다.

코드를 짜는 것은 어렵지 않으나, 풀이 알고리즘을 떠올리는 것이 어려웠다.

절단된 쇠막대기의 개수를 세기 위해 층별로 구분된 막대기에 레이저가 발사된 횟수를 세는 것이 아닌, 하나의 레이저가 발사될 때마다 해당 레이저가 몇 개(층)의 쇠막대기를 절단하고 있는지를 세어서 계산해야 한다.

 

 

로직은 다음과 같다.

 

• ')'이 들어오는 경우는 레이저이거나, 쇠막대기의 끝을 의미한다.
  • ')' 직전의 요소가 '('이라면 레이저, 아니라면 쇠막대기의 끝을 나타낸다.
• 레이저인 경우, 스택에 쌓인 '('의 개수 = 층에 쌓인 쇠막대기의 개수이므로, 남은 스택의 길이만큼 + 해준다.
• 쇠막대기의 끝인 경우, 잘린 후 남은 마지막 끝 부분이므로 +1 만 해주면 된다.

 

 

 

# 괄호를 처음부터 끝까지 탐색하며 괄호가 닫힐 때마다(레이저 or 막대기의 끝) 계산 
# '(' 하나 당 한 칸의 쇠막대기를 의미하며, 레이저가 아닌데 괄호가 닫히는 경우, 쇠막대기의 끝을 나타내므로 + 1
# 레이저인 경우, 해당 레이저가 몇 개의 쇠막대기를 관통하는지 계산
# 현재 스택에 쌓인 '('의 개수가 층으로 겹쳐진 쇠막대기의 개수를 의미하므로 남은 '(' 개수를 세어주면 됨
a = input()
st = []
ans = 0
for i in range(len(a)):
    if a[i] == '(':
        st.append(a[i])
    else:
        st.pop()
        if a[i-1] == '(': # 레이저인 경우
            ans += len(st)
        else: # 레이저가 아닌 경우 = 쇠막대기의 끝을 의미하고, 자르는게 없으므로 그냥 1을 더해주면 됨
            ans += 1
            
print(ans)