백준 10799 - 쇠막대기

문제

알고리즘 분류)

• 자료 구조
• 스택

풀이

스택의 성질을 이용하여 푸는문제
이해하면 구현자체는 힘들지 않지만 문제 이해에 시간이 조금 걸렸다

쇠막대기의 개수를 어떤식으로 더해나가야 할지 고민하다가
레이저가 한번 쏠때마다 앞에서 등장한 '('의 횟수만큼씩 더해지는 것을 알았다
ex) ((( () )))
는 3개의 막대가 2배가되어 6개의 막대기가 생기는 것이다
이것은 +3+3 으로 생각할 수 있다
또한 +1+1+1 +3 으로 생각할 수 있다
앞에서 '('가 등장할 때 마다 +1씩 해주며 현재 스택에 추가해준다
')'가 등장한 바로 이전이 '(' 일 경우 레이저이므로 다시 -1을 해준뒤 여는괄호갯수를 결과값에 더한다
혹은 ')'가 등장한 바로 이전이 ')' 일 경우 그냥 막대기가 끝나는 것이다

소스코드

python)

stack = []
text = input()
sum = 0
for i,name in enumerate(text):
    if name == '(':
        sum += 1
        stack.append(name)
    elif name == ')':
        if text[i-1] == '(':
            sum -= 1
            stack.pop()
            sum += len(stack)
        elif text[i-1] == ')':
            stack.pop()
    
print(sum)

다른 사람들의 코드를 보니 굳이 +1을한 후 -1을 해주지않고 ')'가 나왔을 경우 그때 +1 해주는 방법이
더욱 간단하였다