[백준 알고리즘/Python3] 10799 쇠막대기

문제이해

'()'은 레이저  '('은 쇠파이프 시작 ')' 은 쇠파이프 종료, 처음 봤을 때 스택을 이용해서 풀면 되겠다 생각했습니다.

(은 모조리 스택에 넣고 ) 가 들어오면 pop을 해서 스택에 남아있는 ( 개수를 찾으면 될거라고 생각 했죠. 

문제는 )) 처럼 )가 2개 나오는 경우 입니다. 만약 앞에 (가 온다면 레이저를 쏘는 것이고 )가 오는 것이라면 파이프의 끝이라는 의미입니다.

 

1개의 파이프가 들어와서 레이저를 맞고 끝나면 2개의 파이프가 됩니다. 레이저를 맞은 파이프는 끝날 때 +1이 된다는 것 입니다.

 

코드

input = list(input())
stack = []
result = 0

for i in range(len(input)):
    
    if(input[i] == '(' ):
        stack.append(input[i])
    elif(input[i] == ')'):
        if(input[i-1] == '('):
            stack.pop()
            result += len(stack)
            continue
        stack.pop()
        result += 1
     
print(result)

처음에 list형태로 만들고 바로 for문으로 돌렸는데 바로 이전의 값을 구해야 해서 원본의 index를 조절하는 식으로 했습니다.

')'가 왔을 때 바로 이전의 값이 '(' or ')' 입니다.

• '('면 레이저를 쏴서 파이프의 개수 만큼 파이프가 늘어납니다.
• ')'면 파이프의 끝 이므로 이 때 까지 짤리 파이프의 개수에 +1을 하면 최종 개수를 구할 수 있습니다.

 

마지막 파이프가 끝날 때 +1 하는 개념을 놓치고 있어서 다른 풀이를 참고 했습니다.

참고