[ 파이썬(python) ] 백준 10799 - 쇠 막대기

📍 백준 10799 - 쇠 막대기

문제: 백준 10799 - 쇠 막대기

---

💡 나의 풀이

stack으로 해결할 수 있는 문제이나, 레이저와 쇠 막대기의 관계를 코드로 구현하는데 오래 걸렸다.

 

이 문제를 풀 때 예제는 올바른(짝이 맞는) 괄호만 주어진다는 점을 알고 풀면 접근하기 쉬울 것이다. 또 하나의 깨알 팁은 입력범위가 100,000이라서 import sys를 써야 시간초과가 나지 않는다.

 

1. 여는 괄호(()는 stack에 집어넣는다
2. 닫는 괄호())가 나올 때 쇠 막대기인지 레이저인지 구분해야 하는데, 우선 레이저는 인접한 쌍(즉, 현재 index가 ) 이면 무조건 이전 index는 ()이다. 그럼 나머지의 경우는 모두 쇠 막대기로 판단할 수 있다.
3. 레이저의 경우는 현재까지 들어있는 len(stack)을 구하면 된다.(참고로 stack에 여는 괄호만 들어있다.)
4. 레이저가 아닌 경우(쇠 막대기인 경우)는 누적 cnt 값에 +1을 더해주면 된다.

728x90

이 문제의 관건은 pop()의 시점인데, 레이저의 경우 stack[-1]값을 pop 해주고 len(stack)을 해주고, 쇠 막대기의 경우 cnt += 1 이후 pop을 해주는것이 전체 흐름을 파악하기에 적절하다. (물론 18, 19번째 코드를 뒤바꿔 제출해도 정답이다.)

 

import sys
input = sys.stdin.readline

s = input().rstrip()
stack = []
cnt = 0

for i in range(len(s)):
    if s[i] == '(':
        stack.append('(')

    else:    # ')'
        if s[i-1] == '(':    # Razor
            stack.pop()
            cnt = cnt + len(stack)

        else:    # ')', ironBar
            cnt += 1
            stack.pop()
print(cnt)