[백준] 10799 번 쇠막대기 (스택)

백준 10799

 

백준 10799번 문제입니다.

 

이젠 괄호만 봐도 스택이 생각나버리는...😞

이번 문제는 이해하는게 너무 오래 걸리고 어려워서 글을 작성하게 되었습니다.

 

문제 해결 아이디어

 

괄호 문제의 포인트는 괄호를 스택에 넣고 쌍이 맞게 되면 pop()을 통해 빼내는 방식으로 해내는 것입니다.

 

"(" 기호가 들어오게 되면 쇠막대기가 있거나 or 레이저로 시작점을 자르는 경우가 됩니다.

1. "(" 기호가 들어오고 ")" 기호가 바로 들어오는 경우 -> 레이저로 자르게 되는 경우 (막대의 오른쪽 끝)
2. ")" 만 들어온 경우 -> "(" 기호는 막대의 시작점이 된다. (막대의 왼쪽 끝)

위의 두 아이디어를 가지고 문제의 그림을 다시 봅시다. 

 

()로 괄호가 완성된 시점에서 레이저를 통해 막대를 자를 수 있습니다.

 

첫 번째 괄호 지점에서는 막대가 존재하지 않기 때문에 아무것도 셀 수 없게 되겠죠?

두 번째 괄호 지점을 보면 앞에 존재하는 막대가 총 세개로 나타납니다.

이를 위의 괄호와 함께 보게 된다면

 

()(((()())(())()))(())

레이저 지점은 이렇게 총 6가지로 확인할 수 있습니다.

두 번째 레이저가 동작하는 지점에서 막대의 시작점인 "(" 를 보게 된다면 레이저를 기준으로 왼쪽에 세개의 막대가 존재하는 것을 확인할 수 있습니다. 즉 레이저가 동작하는 지점에서 왼쪽 "("의 기호를 세어주면 막대가 레이저를 기준으로 몇개가 잘렸는지를 확인할 수 있게 됩니다.

 

마찬가지로 세 번째 레이저가 완성되어도 여전히 "(" 기호는 왼쪽에 세개 존재합니다.

 

그리고 파란색으로 표시한 것 처럼 막대가 마무리 된 경우, 왼쪽에 존재하는 "(" 기호는 2개로 막대하나가 마무리되고 막대 두개가 남음을 확인할 수 있습니다.

따라서 막대하나가 마무리 될 때 마지막 도막을 결과값에 +1을 해주면 됩니다.

 

 

정답 코드

위의 아이디어를 바탕으로 파이썬 코드를 작성하였습니다.

import sys
sys.stdin = open("Baekjoon/test.txt", "r")

stick = list(sys.stdin.readline())
stack = []

stick_num = 0
res = 0

# 괄호의 스택 구조는 스택에 하나씩 넣고 ()쌍으로 빼서 -> cnt 변수로 세는 구조
for i in range(len(stick)) : 
    if stick[i] == '(' :
        stack.append(stick[i])
        # = 쇠 막대기의 시작?
    elif stick[i] == ')' :
        if stick[i-1] == '(' :
            stack.pop()
            # 자른 기준으로 앞의 막대 개수(머리개수)를 세면 몇 개 조각이 났는지 알 수 있음.
            res += len(stack)
        else : 
            stack.pop()
            stick_num += 1
            # 마무리 된 것만 하나로 추가해주기
            res += 1

print(res)

 

문제 풀이를 위해서는 res 변수만 선언해주어도 되는데

문제 이해를 위해 stick_num 변수를 추가하였습니다. (원래는 laser_num도 있었던..)