Python으로 푸는 백준 10799. 쇠막대기

괄호로 표현된 쇠막대기와 레이저가 있다.

긴 쇠막대기 위에 작은 쇠막대기를 층별로 쌓았을 때, 레이저를 수직으로 쏘게되면

몇개의 쇠막대기 조각이 나오는지 알아보는 프로그램을 짜시오.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

github에서 코드 보기

문제 풀이

문자열을 순회하면서 어디서부터 레이저이고, 막대기의 시작과 끝인지를 구분할 수 있어야 한다. 

• '(' 의 뒤가 ')'이면 레이저이다.
• '('의 뒤가 '('이면 막대기의 시작이다.
• ')'의 앞이 ')'이면 막대기의 끝이다.

레이저를 발견하면 아직 끝이 닫히지 않은 막대기들은 레이저에 영향을 받아 쪼개질 수 있다. 

• 막대기가 레이저 1개의 영향을 받으면 2개로 쪼개진다.
• 막대기가 레이저 2개의 영향을 받으면 3개로 쪼개진다.
• 즉, 레이저 N개의 영향을 받으면 막대기는 N+1개로 쪼개진다.

막대기의 끝에 도달하여 pop()하게 되는 막대기는 자신이 알고있던 레이저의 수를 아랫부분에 깔려있는 막대기가 있다면 그 막대기에게 알려주고 사라진다. 

파이썬 코드

import sys
input = sys.stdin.readline
 
 
def solve(string):
    stack = []
    count = 0
    for i in range(0, len(string)):
        before_ch = None
        if 0 < i:
            before_ch = string[i-1]
        curr_ch = string[i]
        next_ch = None
        if i < len(string)-1:
            next_ch = string[i+1]
 
        if curr_ch == '(':
            # 레이저
            if next_ch == ')':
                # 스택이 채워져 있으면 막대기가 범위 내에 레이저가 있다는 의미
                if stack:
                    stack[-1] += 1
            elif next_ch == '(':
                # 막대기 시작
                stack.append(0)
 
        elif curr_ch == ')':
            # 막대기 끝
            if before_ch == ")":
                laser_count = stack.pop()
                count += (laser_count + 1)
                if stack:
                    stack[-1] += laser_count
    return count
 
 
 
if __name__ == "__main__":
    print(solve(input().strip()))