백준 알고리즘 - 10799 - 쇠막대기

---

풀이

() : 무조건 레이저

스택 이용

 

틀린 수도코드

if ( : 스택에 ( 넣기
    if 스택의 맨마지막이 ( : 스택에 ( 넣기 
    else 스택의 맨마지막이 ) : 스택에 ( 넣기
else ) :
    if 스택의 맨마지막이 ( : 스택에서 ( 빼고나서 스택에 쌓여있는 ( 개수만큼 더해주기
    else 스택의 맨마지막이 ) : 스택에서 ( 빼고 count +1

틀린 코드

string = input()
n = list(string)
stack = []
cnt = 0
for i in n:
    if i=='(':
        stack.append(i)
    else: # i==')' 
        if stack[-1] == '(': # 스택의 맨 마지막이 (
            stack.pop()
            cnt += len(stack)
        else : # 스택의 맨 마지막이 )
            stack.pop()
            cnt += 1
print(cnt)

( () () ) 의 답은 3이다.

위의 코드가 틀린 이유는 else 문에서

스택의 맨 마지막이 '(' 일 때로 받았기 때문이다.

즉 stack[-1] == '(' 로 조건문을 받았기 때문이다.

 

제일 마지막 ) 괄호에서 스택에는 ( 만 남아있다.

그러면 else 문에서 ( ) 로 받고, 스택에서 ( 를 빼고나서 스택에 쌓여있는 ( 개수만 더해주므로 0을 더해줘서 count가 되지 않는다. 

 

따라서 else 문에서 

스택이 맨 마지막이 '(' 일 때로 받지 말고, 문자열 또는 리스트의 i-1 번째가 '(' 일 때로 받아야 한다.

---

코드

string = input()
n = list(string)
stack = []
cnt = 0
for i in range(len(n)):
    if n[i]=='(':
        stack.append(i)
    else: # i==')' 
        if n[i-1] == '(': # 스택의 맨 마지막이 (
            stack.pop()
            cnt += len(stack)
        else : # 스택의 맨 마지막이 )
            stack.pop()
            cnt += 1
print(cnt)