스택, 큐 추가문제

Question: 유효한 팰린드롬 2

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
• 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

입력: ()(((()())(())()))(())

출력: 17

내 풀이

bar_razor = list(input())
answer = 0
stack = []

for i in range(len(bar_razor)):
    if bar_razor[i] == '(': #스택 쌓기
        stack.append('(')
        
    else:
        if bar_razor[i-1] == '(': #()라면 (를 pop하고 현재 스택에 들어있는 ( 수만큼 값을 더해준다.
            stack.pop()
            answer += len(stack)
            
        else:
            stack.pop() 
            answer += 1 #끄트머리 막대기 부분을 더해준다

print(answer)

다음과 같은 세가지 조건을 만족하는 코드이다.

1. ’(‘이 나오면 스택에 넣는다.
2. ’()’이 나오면 현재 스택에 있는 ‘(‘ 수만큼 정답에 더해준다.
3. ’)’ 이 나오면 스택의 ‘(‘를 pop하고 정답에 1을 더해준다.

위의 입력 값에 대해서는 3+3+1+3+1+2+1+1+1+1 의 계산 과정을 거쳐서 답이 17이 나오게 된다.

결과

메모리: 32076 KB
시간: 92 ms