[알고리즘] 백준 - 쇠막대기

백준 쇠막대기

내 풀이

sentence = input()
count  = 0
stack = []

for i in range(len(sentence)):
    if sentence[i] == "(":
        stack.append("(")
    else:
        if sentence[i-1] == "(":
            stack.pop()
            count += len(stack)
        else:
            stack.pop()
            count += 1

print(count)

처음 봤을 때는 스택을 어떻게 응용해야하는건지 떠오르지 않았었다. 스택 문제가 직관적으로 스택을 써야겠다고 떠오르지 않는 문제가 꽤 있는 것 같다. 풀이는 ")"이 나오는 경우 직전에 "("가 나오면 레이저로 자르는 것이고, 그것이 아니라면 그냥 쇠 막대기가 끝나는 지점이다. 따라서 자를 때는 그냥 스택에 있는 쇠 막대기만큼 개수를 더해주면 되고, 쇠 막대기가 끝날 때는 하나만큼만 전체 개수에 더해주면 된다.