[BOJ] 10799번 - 쇠막대기

---

문제설명

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

10799번: 쇠막대기

사고과정

• 또 괄호 문제였는데 이번엔 풀지 못했다..
• 스택을 활용하는 문제였는데, ( 가 등장할 때마다 스택에 넣고 )가 등장할 때는 )가 등장하기 이전에 (가 등장했으면 레이저용 괄호로 간주하고 스택의 마지막 (를 pop해주고 남은 스택의 길이 만큼이 해당 레이저로 의해 잘려지는 막대 개수이다. 만약 이전에 ) 가 또 등장했다면 연속적인 쇠막대기의 등장인 것이므로 스택의 마지막 (를 pop해주되 잘려지는 막대를 1개만 더해준다.
• 앞으로 문제를 보면 의식적으로 큐, 스택같은 자료구조를 활용해야 겠다고 생각하고 풀어봐야겠다. 그냥 막연히 어떻게 구현해야 할까에 대한 생각보다 컴퓨터 자료구조 입장에서 풀이를 생각해보자!

풀이(스스로 못 푼 풀이)

bar = list(input())
stack = []
answer = 0
# 괄호가 무조건 ( 부터 나온다고 하기 때문에 loop안에 i-1 인덱싱있더라도 index out of range 에러 발생 안 함!
for i in range(len(bar)):
    if bar[i] == '(':
        stack.append('(')
    else:
        if bar[i-1] == '(':
            stack.pop() # 레이저용 ( 괄호를 스택에서 pop
            answer += len(stack)
        else:
            stack.pop() # 다음 짝지어진 쇠막대기 카운트 위해서 ( 스택에서 pop
            answer += 1

print(answer)

 

푼지 시간이 지나고 풀이를 안보고 풀었는데 while 문을 사용해서 풀었다.. 좀 불필요한 로직들이 많이 추가되었다.. 시간이 지나도 어렵다..

string = input()
stack = []  # 스택에는 괄호'(' 넣기!
count = 0
index = 0
while index < len(string):
    if string[index] == '(':
        stack.append(string[index])
        index += 1
        while stack and string[index] != ')':
            stack.append(string[index])
            index += 1
        # ')'만났을 경우
        stack.pop()
        count += len(stack)
        index += 1   # ')' 다음의 인덱스로!
    else:
        stack.pop()
        count += 1
        index += 1  # ')' 다음의 인덱스로!

print(count)


#=======
#원래 풀이
#=======
string = input()
count = 0
stack = []
for i in range(len(string)):
    if string[i] == '(':
        stack.append('(')
    # ')'나왔을 경우
    else:
        # string의 이전 인덱스 위치에 '('인 경우
        if string[i-1] == '(':
            stack.pop()
            count += len(stack)
        # string의 이전 인덱스 위치에 ')'인 경우
        else:
            stack.pop()
            count += 1

print(count)