백준 10799 쇠막대기.py

풀이 논리 

 

1. 레이저는 두 괄호가 붙어서 등장한다. 따라서 "(" ")" 가 연속으로 인식되면 이를 레이저로 처리할 수 있다.

2. 레이저는 지금까지 등장한 막대기를 잘라낸다. 따라서 등장한 막대기의 개수만큼 누적값을 증가시킬 수 있다.

3. 막대기의 종료점이 등장하는 경우, 해당 막대기가 잘려나가는 효과와 동일하므로 누적값을 +1 증가시킬 수 있다.

4. 막대기가 등장해서, 종료되기 전까지 이 열린 괄호를 스택에 관리한다. 

 

정답 코드

input = input()
stack = [] 
answer = 0
temp = ''

for i in input:
    if i == '(':
        stack.append("(")

    elif i == ')' :
        stack.pop()
        if temp == '(':
            answer += len(stack)
        else:
            answer += 1
            
            
    temp = i

print(answer)

 

오답 코드

input = input()
stack = [] 
answer = []
a = 0
temp = ''
for i in input:
    stack.append(i)
    if i == '(':
        temp = '('
        answer.append(1)
    if i == ')' :
        stack.pop()
        stack.pop()
        if temp == '(':
            answer.pop()
            for j in range(len(answer)):
                answer[j] += 1
        else:
            a += answer.pop()
    temp = i
print(a)

 

중간에 시간초과가 발생하여 알 수 없지만, 중간에 answer이라는 리스트 for문으로 탐색하게 하며 시간 초과가 났다.

이 풀이는 막대기가 종료되는 지점에서 어떻게 관리해야하는지 잘못 생각해서 나온 것으로.. 동작방식의 잘못된 이해에서 비롯되어있다 (...)

꼼꼼히 생각하자 ..