[Python] BOJ 10799 : 쇠막대기

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

생각해보기

• 어떻게 래이저와 쇠막대기를 구별할까?
  • ')' 이 들어올 때, 그 전이 '(' 라면 레이저이다.
  • ')' 이 들어올 때, 그전이 ')' 라면 막대기의 끝이다. 

요구사항

• 시간제한 1초 : 여기서 N은 <= 100,000이니 O(N**2) 전 까지는 괜찮을듯
• 메모리제한 256MB 항상 넉넉한 편인듯
• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. -> 괄호로 표기할 떄 병렬로 하지 못하니깐 당연하다.
• 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어질 떄, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램

설계

• def count_sticks():
  • 사용자로부터 괄호를 입력 받는다.
  • 빈 리스트를 초기화 한다. ( 스택 초기화 )
  • 결과를 저장할 변수를 초기화 한다.
  • for i in range(len(bars): # 괄호의 길이만큼 반복한다.
    • 만약 bars[i] 가 '('라면 
      • 빈 리스트. append('('); 
    • 아니라면. 즉, ')' 라면 # 막대기 끝 또는 레이저
      • if bars[i-1] == '(' 라면. 즉, ( ) 이니 레이저 라면 !!
        • stack.pop() # stack 에 저장된 '(' 는 레이저를 위한 것... '(' 를 pop
        • 결과 변수 += stack의 길이 
      • else: 즉, bars[i-1] != '(' 라면. 즉, 막대기의 끝이므로 하나 pop
        • stack.pop() # 막대기의 끝이므로 하나 pop
        • 결과 변수 += 1 # 하나의 조각 추가
  • 결과 변수를 출력

구현

def count_sticks():
    bars = input().strip()
    stack = []
    result = 0

    for i in range(len(bars)):
        if bars[i] == '(':  # 막대기 시작
            stack.append('(')
        else:  # 막대기 끝 또는 레이저
            if bars[i-1] == '(':  # 레이저
                stack.pop()  # 레이저는 막대기의 시작을 나타내는 '('을 pop
                result += len(stack)  # 스택에 있는 막대기 개수만큼 더함
            else:  # 막대기 끝
                stack.pop()  # 막대기의 끝이므로 하나 pop
                result += 1  # 하나의 조각 추가

    print(result)
    
 count_sticks(input())

• 괄호 문자열을 순차적으로 탐색 
• ( 를 만나면 스택에 추가
• )를 만날 때, 이전 문자가 ( 일 경우 레이저로 판단. 스택에 남아 있는 쇠막대기 수 만큼 조각이 생긴다.
• 그 외에는 스택에서 ( 를 하나 제거하고 마지막 쇠막대기의 끝 부분을 조각으로 더해준다.