[Python] 10799번 쇠막대기

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

 

막대기를 레이저로 자릅니다!

 

input은 ((()()(()))) 이런 식으로 구성되어 있습니다.

사실 이런 괄호 더미가 나오면 바로 스택부터 생각이 납니다.

아무튼 input은 한 줄인데 막대기와 레이저를 어떻게 구현한 걸까요?

 

일단 괄호의 길이가 100,000개이니 O(n)이나 O(n*logn)의 풀이를 생각해야겠네요

문제 풀이1 :

 

()로 붙어있는 괄호세트는 레이저고 떨어져 있는 괄호는 막대기입니다.

레이저가 지나가면 막대기가 조각나기 때문에 겹쳐진 막대기 만큼 막대기 개수에 더해주면 됩니다.

 

그럼 겹쳐진 막대기를 어떻게 구하나요?

 

'('을 스택에 쌓고 ')'이 나오면 스택을 뺍니다.

'()'가 나와서 레이저가 쏴지면? 그때 쌓인 스택의 길이는 잘리는 막대기의 수와 같습니다.

 

import sys

input = sys.stdin.readline

arr = list(input().rstrip())
n = len(arr)

lazer = 0
stack = []

for i in range(1,n,1):
    if arr[i-1] =='(':
        lazer+=1
    if arr[i-1] == '(' and arr[i] ==')':
        lazer-=1

answer = lazer

for i in range(n):
    if arr[i] == '(':
        stack.append(i)
        continue

    index = stack.pop()
    if index + 1 == i:
        answer += len(stack)

print(answer)

 

풀이 과정

 

1. 일단 막대기 개수를 구한다. '(' 개수가 나오면 막대기 개수 +1, '()'이 나오면 막대기 개수 -1

2. input을 넣은 배열을 하나씩 확인한다.

3. 배열이 '('이면 무지성 index 번호를 스택에 쌓는다.

4. ')'이 나오면 스택을 pop하고 하나 꺼낸다. 현재 index와 앞의 '(' index를 확인하고 차이가 1인지 확인한다.

4-1. 1이 아니면 그냥 지나간다.

4-2. 1이면 '()'이기 때문에 레이저가 발사되었다. 레이저가 발사될때 스택의 길이는 잘리는 막대기의 개수와 같다.

잘리는 막대기 수 만큼 막대기 수가 늘어나기 때문에 정답에 스택의 길이만큼 더한다.

 

5. 정답출력

 

 

코딩테스트 봤다가 스택문제 못풀어서 떨어져서 화난김에 풀어봤습니다...