BOJ 10799 - 쇠막대기

folder_open Algorithm / BOJ / silver | date_range last modified at / created at 11 Oct 2024

sell #BOJ #10799 #silver #python #파이썬 #코딩테스트 #알고리즘

맨 위로

• 문제 링크
• 구현
• 코드

문제 링크

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

구현

스택을 이용하는 문제이다. 중첩 되어있는 막대기를 어떻게 계산을 할 지 고민했는데, 그림을 잘 살펴보니 알 거 같았다.
만약 레이저(‘()’)가 나오면, 여태껏 중첩되어있는 막대기의 개수만큼 총 개수가 늘어난다. 만약 막대기의 끝 (‘)’) 이 나오면, 해당 막대기가 끝나는 것이므로 총 개수가 하나 늘어나며 중첩되어있는 막대기의 수가 하나 줄어든다.

따라서 먼저 ‘()’를 찾아 다른 문자 (‘|’) 로 바꿔주었고, 총 분기를 (, ), | 3개로 나눠 구현했다.

코드

from sys import stdin
input = lambda : stdin.readline().strip()

bar = input().replace('()', '|')
count = 0
stack = []
for i in bar:
    if i == '|':
        count += len(stack)
    elif i == '(':
        stack.append(i)
    else:
        count += 1
        stack.pop()
print(count)