[백준10799] 쇠막대기

https://www.acmicpc.net/problem/10799

 

 

 

문제 해결 방법

0. 카운트 변수를 만든다. 초기화는 0으로 한다. 

1. 받은 문장을 한글자씩 순회하며  현재 열려있는 괄호를 스택에 넣는다. (flag 표시를 해준다 flag = 1)

2. 문장을 순회하다가 닫는 괄호가 나오면 바로 직전에 본 글자가 열려있는 괄호인지 확인한다. (확인은 flag를 통해서 한다. )

 2-1. flag가 1이면 레이저로 확인되었으므로 그동안 열려있는 괄호의 수만큼 카운트 변수에 +1을 해준다. 

 2-2. flag가 0이면 단순 닫는 flag이니 괄호를 닫아주되(들어가있는 값중 -1 인덱스의 값이 열린괄호가 있으면 pop), 하나의 종이를 레이저가 한번 자르면 종이가 n개면 +1이 된다는 것을 고려하여 카운트값에 +1을 해준다.  

 

3. 순회가 끝날 때 까지 2번을 반복한다. 

 

 

 

코드 구현

정답 코드 

# ()는 레이저다 

s = input()
stack=[]
cnt = 0
flag=0
for i in s:
    if i =='(':
        stack.append('(')
        flag=1
    elif i==')':
        if stack[-1] =='(':
            stack.pop()
            if stack and flag==1:
                if flag ==1:
                    cnt+=len(stack)
            if flag ==0:
                cnt+=1
            flag=0


    # print('난 ',i,'에요', stack, 'cnt: ', cnt)
print(cnt)

 

시간/공간 복잡도

괄호 문자는 최대 100,000 이므로, O(NlogN)으로 풀어야한다. 

최적화 및 개선

따로 하지 않음 

어려웠던 점

없음

 

알게된 것

따로 없음