[BOJ/백준] 10799번 쇠막대기 | 스택 | 파이썬

문제

풀이

import sys

def cutIron(bar):
    stack = []
    cnt = 0
    for i in range(len(bar)):
        if bar[i] == '(':
            stack.append('(')
        elif bar[i] == ')':
            if bar[i-1] == '(':
                stack.pop()
                cnt += len(stack)
            else:
                stack.pop()
                cnt += 1
    return cnt
bar = list(sys.stdin.readline())
print(cutIron(bar))

 

스택 자료구조를 사용한 문제.

 

입력으로 받은 문자열을 리스트 bar로 바꿔 쇠막대기 개수를 세는 함수 cutIron에 넣었다.

 

bar의 길이만큼 반복문을 수행한다.

1) bar[i] 값이 '('이면 쇠막대기의 시작을 의미하기 때문에 stack에 '('을 넣는다.

 

2) bar[i] 값이 ')'이고 bar[i-1]이 '('인 경우

• 레이저를 의미하기 때문에 stack에서 '('를 꺼낸다.
• stack의 길이(현재 쇠막대기의 개수)만큼 cnt에 더한다.

 

3) bar[i] 값이 ')'이고 bar[i-1]이 ')'인 경우

• 쇠막대기의 끝을 의미하기 때문에 stack에서 '('를 꺼낸다.
• 쇠막대기의 끝을 세기 위해 cnt에 1을 더한다.

 

문자열을 활용한 풀이

import sys

def cutIron(bar):
    bar = bar.replace('()','-')
    tmp = 0
    res = 0
    for i in bar:
        if i == '(':
            tmp += 1
            res += 1
        elif i == '-':
            res += tmp
        else:
            tmp -= 1
    return res
bar = sys.stdin.readline()
print(cutIron(bar))

 

풀이법을 더 찾아보니 문자열을 활용하는 방법도 있었다.

여기서는 replace()를 사용해서 레이저를 다른 문자로 바꾼 후 반복문을 사용해 계산했다😮

 

---

백준 10799번: 쇠막대기

10799번: 쇠막대기