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

해당 문제는 다음과 같은 알고리즘으로 풀이했다.

• 레이저는 ()로 표시되어 있다. 따라서 ()부분을 모두 문자 L로 바꾼다. (.replace() 메서드 사용)
• 주어진 문자열(formula)를 탐색한다. 이때 '('부분은 막대가 시작하는 부분으로 막대가 시작하는 부분이 나오면 num_stick에 1을 더해준다. (num_stick은 현재 구간에 있는 막대 개수다.)
• 문자열 탐색 도중 ')'를 만난다면 가장 짧은 막대기 하나가 끝나는 부분이다. 따라서 num_stick에 -1을 해주고, 지금까지 세어준 막대기(result)에 +1을 한다.
• 만약 'L'을 만나면 result에 num_stick을 더해주면 된다. (현재 구간에 쌓여있는 막대 개수만큼 레이저로 잘리기 때문이다.)

코드는 다음과 같다.

formula = input().rstrip()

formula = formula.replace('()', 'L');

result = 0
num_stick = 0

for char in formula:
    if char == 'L':
        result += num_stick
    elif char == '(':
        num_stick += 1
    else:
        num_stick -= 1
        result += 1

print(result)

만약 .replace를 사용하고 싶지 않다면, ()가 레이저임을 판단하기 위해 ')'를 만났을 때 이전 문자가 '('임을 판단할 수 있어야한다. 만약 이렇게 코드를 작성하고 싶다면 다음과 같이 작성할 수 있다.

formula = input().rstrip()

last = ''
result = 0
num_stick = 0

for char in formula:
    if char == '(':
        num_stick += 1
    else:
        num_stick -= 1
        if last == '(':
            result += num_stick
        else:
            result += 1
    last = char

print(result)

---

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