10799번 쇠막대기 / 스택

자료구조 : 스택

n = input()

stack = []
count = 0
for i in range(len(n)):

    #"(" 라면 스택에 추가
    if n[i] == "(":
        stack.append(n)

    #")" 라면 스택에서 쌍을 이루는 "("를 제거 후, stack의 길이만큼 조각 추가
    else:
        stack.pop()
        #바로 앞의 값이 "("라면 문자열의 끝이 아니므로 길이만큼 추가
        if n[i-1] == "(":
            count += len(stack)
        #문자열의 끝
        else:
            count += 1

print(count)

 

이 문제는 처음에 보고 쇠막대기랑 레이저 사진때문에 머리가 아파서 여러 번 미뤘던 문제다....

조각의 수를 어떤식으로 처리해서 추가해야할지 감을 못 잡아서 풀기 어렵겠다는 결론이 나왔다

결국 찾아본 결과

 

접근방법

• ()  이런식으로 연속된 가로로 있는 경우, 이것이 레이저이다. 이때 이 연속된 가로를 제거 후 해당 stack의 길이(나무토막의 길이)만큼 count에 추가해 주면 된다
• "("이 경우는 stack에 계속 추가하면 된다
• 마지막 연속된 괄호인 경우 마지막 조각인 1을 추가한다

Step  Input       Stack         Action                Total Pieces
1     ()          []            레이저 → +0          0
2     ((((()      [(((((]       여는 괄호 추가        0
3     ()          [((((]        레이저 → +4          4
4     )           [(((]         쇠막대기 끝 → +1     5
5     (())        [(((]         쇠막대기 끝 → +2     7
6     (()         [((]          레이저 → +3          10
7     (())        [ ]           쇠막대기 끝 → +7     17

쉽지 않다.. 문제를 보면 어떤 식으로 접근해야 할 지 아직 많이 부족한 것 같다

그래도 조금씩이라고 하면 달라질거라는 마음을 가지고 ㄱㄱㄱㄱ!!