[알고리즘 문제 풀이][파이썬] 백준 10799번: 단어 뒤집기 2

백준 10799 문제 링크: https://www.acmicpc.net/problem/10799

📑 문제 설명

절단된 쇠막대기의 개수를 파악하는 프로그램 작성하기

• '()': 레이저로, 쇠막대기를 절단하는 지점이다.
• '(....)': 쇠막대기, 긴 쇠막대기가 짧은 쇠막대기를 포함할 수 있다.
• 따라서 () 표시는 레이저를 의미하며 절대 쇠막대기를 의미하지 않는다.

입력: 쇠막대기와 레이저의 조합으로 이루어진 문자열
출력: 절단된 쇠막대기 개수

💡 문제 해결 방법

1. stack 사용
2. 절단된 쇠막대기의 개수를 세는 규칙 찾기.
   

• 레이저를 만날 경우 stack에 쌓인 '(' 수만큼 쇠막대기가 절단된다.
• ')'를 만날 경우, 쇠막대기의 끝지점을 의미하며 1개만 절단된다.

1) '('를 만났을 때,

• 다음 문자열이 ')'일 경우 --> 레이저: 따라서 stack에 쌓인 개수만큼 쇠막대기가 생김
• 다음 문자열이 ')'가 아닐 경우 --> 쇠막대기: stack에 push

2) ')'를 만났을 때,

• 쇠막대기 끝지점을 의미 --> 쇠막대기: stack에 pop을 함과 동시에 쇠막대기 1개 생성

💻 코드

import sys


def count_iron(iron):
    stack = list()
    cnt = 0
    i = 0
    while (i < len(iron)):
        if (iron[i] == '('):
            if (iron[i+1] == ')'):
                cnt += len(stack)
                i += 2
            else:
                stack.append(iron[i])
                i += 1
        elif (iron[i] == ')'):
            cnt += 1
            stack.pop()
            i += 1

    return cnt


if __name__ == '__main__':
    iron = sys.stdin.readline()
    iron = iron[:len(iron)-1]
    result = count_iron(iron)
    print(result)

💟 추가적으로 알게 된 점

• sys.stdin.readline은 마지막 개행문자를 포함하기 때문에 입력을 받을 때 개행문자를 제외하거나 개행문자 예외처리가 필요하다.