[백준 10799 파이썬/python] 쇠막대기

쇠막대기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	42096	26868	19917	64.371%

문제

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.

• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.

• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.

1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.

2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

입력

한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.

출력

잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.

예제 입력 1

()(((()())(())()))(())

예제 출력 1

17

예제 입력 2

(((()(()()))(())()))(()())

예제 출력 2

24

답안

def main():  # 메인 함수를 정의합니다.
    a = input().strip()  # 사용자로부터 입력을 받아 공백을 제거합니다.
    n = len(a)  # 입력받은 문자열의 길이를 구합니다.
    s = []  # 괄호의 인덱스를 저장할 스택을 초기화합니다.
    ans = 0  # 정답을 저장할 변수를 초기화합니다.
    
    for i in range(n):  # 문자열의 길이만큼 반복합니다.
        c = a[i]  # i번째 문자를 가져옵니다.
        
        if c == '(':  # 여는 괄호인 경우
            s.append(i)  # 스택에 인덱스를 추가합니다.
        else:  # 닫는 괄호인 경우
            if s[-1] + 1 == i:  # 직전 문자가 여는 괄호인 경우
                s.pop()  # 스택에서 꺼냅니다.
                ans += len(s)  # 현재 스택의 길이를 정답에 더합니다.
            else:  # 직전 문자가 닫는 괄호인 경우
                s.pop()  # 스택에서 꺼냅니다.
                ans += 1  # 정답에 1을 더합니다.
    
    print(ans)  # 최종 정답을 출력합니다.

if __name__ == "__main__":
    main()  # 메인 함수를 실행합니다.

⭐️’__main__’, ‘__init__’의 의미

파이썬에서 밑줄 두 개(__)로 시작하고 끝나는 이름은 특별한 의미를 갖는 경우가 많습니다. 이러한 이름은 특별한 메서드나 변수를 표현할 때 사용되며, 파이썬에서 사전 정의된 의미를 가지고 있습니다.

__main__

__main__은 파이썬 스크립트를 실행할 때, 스크립트의 시작점을 나타내는 특별한 이름입니다. 파이썬 스크립트를 직접 실행할 때 __name__ 변수는 "__main__" 값을 가집니다. 이를 이용해 스크립트가 직접 실행될 때만 특정 코드를 실행하도록 할 수 있습니다.

예를 들어, if __name__ == "__main__": 구문은 현재 스크립트가 직접 실행되는 경우에만 main() 함수를 실행하도록 합니다. 이렇게 하면 스크립트가 다른 코드에서 모듈로 임포트될 때, main() 함수가 자동으로 실행되지 않아 원치 않는 동작을 방지할 수 있습니다.

__init__

__init__ 메서드는 클래스의 인스턴스를 생성할 때 호출되는 초기화 메서드입니다. 클래스를 정의할 때, 인스턴스 생성 시 수행할 작업이 필요한 경우 __init__ 메서드를 구현합니다. 이 메서드는 생성자(constructor)와 비슷한 역할을 합니다. __init__ 메서드는 인스턴스 생성 후 자동으로 호출되며, 인스턴스의 초기 상태를 설정하는데 사용됩니다.

Uploaded by N2T