10799. 쇠막대기

백준 10799. 쇠막대기

풀이과정

가장 먼저 아래 그림에서 레이저의 좌표와 쇠막대기의 좌표를 어떻게 저장할 수 있을까를 고민함

1차 시도

1. 좌표에 영향을 주는 괄호 : '('와 쇠막대기를 표시하는 ')'가 좌표에 영향을 줌 -> '(' , 쇠막대기를 표시하는 ')'가 나올 때 마다 pointer를 1씩 증가시킴
2. 쇠막대기를 만드는 ')'와 레이저를 만드는 ')'를 구분해야 함
3. 괄호 문자열을 읽어가면서 '('가 나올때마다 그 위치를 스택에 저장해놓았다가 만약 ')'를 만났을 때 '('의 위치와 현재 위치가 같으면 레이저로 구분
4. 레이저와 쇠막대기의 좌표를 모두 구한 후 반복문으로 각각의 쇠막대기 사이에 레이저가 존재하는 횟수+스틱의 개수로 답을 구함 -> 시간초과

import sys

brackets = list(sys.stdin.readline()[:-1])

stick_stack = []
sticks = []
razers = []
pointer = 0

for i in range(len(brackets)):
    if brackets[i] == ')':
        if (stick_stack[-1] == pointer):
            razers.append(pointer)
            stick_stack.pop()
        else: 
            pointer += 1
            sticks.append([stick_stack.pop(), pointer])
    else:
        pointer += 1
        stick_stack.append(pointer)
        before_pointer = pointer
        
        

answer = 0

for s in sticks:
    for r in razers:
        if (s[0] < r < s[1]):
            answer += 1
            
answer += len(sticks)
print(answer)

print(sticks) # [[4, 7], [8, 10], [3, 12], [2, 13], [14, 16]]
print(razers) # [1, 5, 6, 9, 11, 15]

2차 시도

1. 레이저와 쇠막대기를 구하는 과정은 괄호 문자열을 한 번만 체크하기 때문에 시간을 줄일 수 없음
2. 괄호 문자열을 체크하는 과정에서 레이저가 등장할 때마다 스택에 있는 쇠막대기의 개수를 구하면 반복문을 사용하지 않고 답을 구할 수 있음
3. 이렇게 답을 구할거였으면
   (1). pointer 변수도 굳이 필요 없었음. barckets[i-1] == '(' 이 코드로 레이저인지 쇠막대기인지 구분 할 수 있음.
   (2) stick_stack 도 굳이 만들필요 없이 그냥 숫자 올리고 내려도 됬음

import sys

brackets = list(sys.stdin.readline()[:-1])

stick_stack = []
sticks = 0
pointer = 0
answer = 0

for i in range(len(brackets)):
    if brackets[i] == ')':
        if (stick_stack[-1] == pointer):
            stick_stack.pop()
            answer += len(stick_stack)
        else: 
            pointer += 1
            stick_stack.pop()
            sticks += 1
    else:
        pointer += 1
        stick_stack.append(pointer)
        before_pointer = pointer
        
answer += sticks
        
print(answer)

최종

import sys

brackets = list(sys.stdin.readline()[:-1])

sticks_now = 0
sticks = 0
answer = 0

for i in range(len(brackets)):
    if brackets[i] == ')':
        if (brackets[i-1] == '('):
            # 레이저 표시
            sticks_now -= 1 # 현재 스틱 개수 감수
            answer += sticks_now # 잘린 스틱 개수 추가
        else: 
            # 쇠막대기 끝 표시
            sticks_now -= 1 # 현재 스틱 개수 감소
            sticks += 1    # 총 스틱 개수 증가
    else:
        # '(' 나오면 stick 개수 추가
        sticks_now += 1

answer += sticks
        
print(answer)