자료구조 중에서 자주 쓰이는 stack을 활용한 백준 문제를 풀어보았다.
괄호(Valid PS)문제와 비슷하게 괄호와 연관되어 있는 문제였으며 해당 풀이를 적어 보려한다.

🧐 문제 분석 및 구현 요소

아래가 문제에 대한 전반적인 설명이다.

자료구조 방식은 이전 풀이하였던 괄호 문제와 유사하며 닫히는 괄호( ) )를 만났을 때 계산이 이루어지기 때문에 가장 먼저 스택을 사용해보기로 했고, 단순한 풀이를 생각했을 때 큰 어려움이 없을 것이라 생각했다.

문제의 설명을 읽어보면 몇 가지 주의 사항 및 괄호 배치(입력)에 따른 쇠막대기 갯수(출력)을 어떻게 산출해내는지에 대해 설명하고 있다. 그 중 가장 먼저 괄호 배치에 따라서 어떻게 레이저와 쇠막대기를 구분해야하는 지 알 필요가 있다.

레이저와 쇠막대기의 구분 방식은 아래와 같다.

• 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '( )' 으로 표현된다. 또한, 모든 '( )'는 반드시 레이저를 표현한다.
• (중요!) 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 ')'로 표현된다.

이러한 구분 방식과 위의 몇 가지 추가 설명에 따라 나는 4가지의 필요 조건을 생각하고 적어두었다.

1. ( )이 비로소 레이저를 뜻하기 때문에 ( 을 더해가다가 )을 만나면 그 순간 앞에 있는 막대기( ( )의 개수에 따라 절단이 이루어진다.
2. ( ) 이후 ) 이 하나 더나온다면 이것은 레이저가 아니라 막대기의 끝을 의미한다. 이때를 구분하는 코드가 들어가야한다.
   2-1 . 막대기의 끝을 만나면 비로소 그 막대기는 더 이상 사용하지 않기 때문에 +1만을 더해야한다.
3. 전체 막대기의 절단 개수를 세고 이걸 변수에 넣는다.

여기서 가장 고민했던 건 레이저가 출력되고 난 뒤에 바로 막대기의 끝이 나올 때 이를 어떻게 구분할 것이냐였다.

평소 리스트의 인덱스를 통한 값의 접근을 자주 사용했던 편이라 리스트의 인덱스를 생각해 코드를 작성했지만 out of range 에러가 빈번히 발생해 끝끝내 인덱스 기능을 포기하고 처음부터 다시 작성해보기로 했다.

📗 Programming

💻 Main

import sys 

stack = []
result = 0
chg = 0			# 여는 괄호, 닫는 괄호에 따라 상태를 저장해줄 변수.

for i in sys.stdin.readline().strip():
    if i == '(':
        stack.append('(')
        chg = 1			# 여는 괄호가 입력되면 chg 변수의 값을 1로 변경.
        
    if i == ')':
        if chg == 1:
            stack.pop()
            result += len(stack)
            chg = 0			# 닫는 괄호가 입력되면 chg 변수의 값을 0으로 변경.
        elif chg == 0:
            stack.pop()
            result += 1
            
print(result)

가장 문제에서 생각을 많이 하게 한 부분은 레이저 뒤에 막대기의 끝이 나오는 경우( '( ) )' )였다.

막대기의 끝을 통해 1을 더해주는 부분에는 이전 괄호에 대한 상태값이 필요했고 이는 인덱스를 활용하는 방법보다 하나의 변수를 할당해 이 변수의 값을 스위치해주는 방법이 더 편리하고 용이했다.