baekjoon. 쇠막대기 (10799) [python][Silver II]

문제 링크 : https://www.acmicpc.net/problem/10799

 

문제 풀이 

sticks = input()

stack = []
count = 0
for i in range(len(sticks)):
    cur = sticks[i]

    # ( 만나면 stack push 
    if (cur == '('):
        stack.append(cur)

    # 최상단이 (이고 그 다음이) 이면 size 추가 
    # ) 만나면 1 추가 
    elif (cur == ')'):
        stack.pop()

        if (sticks[i - 1] == '('):
            count += len(stack)
        else:
            count = count + 1

    # print(i, ' : ', cur, ' - ', count)

print(count)

 

---

((( () () ))) 를 예시로 보면, 각각의 기호는 다음과 같은 역할을 한다고 볼 수 있다. 

- () : 막대기 자름 

- ( : 막대기 새로 생성 

- ) : 막대기 새로 생성 (종료) 

 

 

 

- ((( : 3개 막대기 새로 생성한다. 

- () : 자르면서 막대기 3개를 만든다 

- () : 또다시 자르면서 막대기 3개를 만든다 

- ))) : 3개 막대기 새로 생성 (=종료) 한다. 

 

 

 

결과적으로는 아래와 같은 그림을 그릴 수 있다. 

 

 

 

그래서 이 로직을 규칙으로 풀어보면, 아래와 같다. 

1. (를 만나면 스택에 (를 추가한다. 

2. )를 만나고 스택의 최상단이 (이었으면, 이면 스택의 크기만큼 갯수에 추가한다. 

3. )를 만나면, 갯수에 1을 추가한다.