스택을 활용한 문제이며, 동작 과정에서 괄호값을 계산해야하는 것이 해당 문제의 포인트이다. () 쌍의 값은 2, [] 쌍의 값은 3이라는 간단한 규칙을 갖고 있지만 괄호 안에 괄호가 종속되어있는 형태 (예: [[()]]
)의 경우에는 값을 곱하고 (예:3X3X2), 괄호가 나란히 결합되어있는 형태 (예 : ()[]
)라면 값을 더한다. (예:2+3)
아래 입력 예제를 보면서 어떻게 풀이해 나가야 하는지 생각해보자. 앞으로 종속되어있는 형태는 (X)종속형태로 표현하고, 결합되어있는 형태는 XY결합형태로 표현하겠다.
입력 예제 : (()[[]])([])
(()[[]])([])
를 크게 둘로 쪼개면 (()[[]])
와 ([])
이다. 앞의 (()[[]])
를 살펴보자. 이 형태는 내부를 뜯어보면 단순히 (X)종속형태만 있는 것이 아니라 XY결합형태도 존재한다. 그렇다면 계산 도중에 종속형태와 결합형태를 어떻게 구분할 수 있을까?
일단 처음엔 열린괄호를 마주할 때마다 스택에 해당 괄호를 추가하고 tmp에 값을 계속 곱해간다. 가장 내부에 있는 쌍의 닫힌 괄호를 마주할 때까지 반복한다. 이 개념이 key point인데, 가장 내부에 있는 쌍을 마주하면 종속 형태 하나가 끝났다고 볼 수 있기 때문이다.
X인 (()[[]])
로 생각해보면 가장 내부에 있는 쌍은 (()[[]])와 (()[[]])이다. 즉, 가장 내부에 있는 쌍은 닫힌 괄호를 마주했을 때 바로 직전의 괄호와 짝이 맞는 경우를 의미한다.
X를 직접 계산해보자. 처음 열린괄호 ( 를 마주했을 때 tmp값은 2, 그 다음 열린괄호 (를 마주했을 때 tmp값은 2X2이다. 그 다음은 닫힌괄호 ) 인데 가장 내부에 있는 쌍이므로 종속형태 하나가 끝났음을 의미한다. 종속형태가 끝났다는 것은 이후 남은 괄호들과는 무조건 결합형태로 시작될테니 지금까지의 tmp 계산을 마무리해서 최종 결과 값을 담는 변수에 더해준다.
여기서 빼먹으면 안되는 것이 계산이 마무리되었다고 스택을 pop하고 tmp값을 1로 초기화하는 것이 아니라, 닫힌 괄호를 마주할 때마다 tmp값을 괄호쌍의 유형에 맞게 2나 3으로 나눠주어야한다는 점이다. 이 개념이 2번째 key point이다. 그래야만 (()[[]])
에서 (())
를 계산한 후에,[[]]
이 친구도 겉에 부모 괄호가 있다는 것을 인지할 수 있다. ([[]])
이런 식으로 말이다.
이해가 바로 되지 않는다면 초등학교때 배웠던.. 곱셈 분배법칙을 떠올려봐도 좋을 것 같다. (()[[]])
를 계산식으로 나타내면 2X(2+3X3)인데, 이를 분배법칙으로 나타내면 (2X2) + (2X3X3) 이다. 결합형태와 종속형태가 섞여있으면 바로 이해하기 힘드므로 (()[[]])
를 (())
과 ([[]])
의 결합형태로 보자는 뜻이다. ([[]])
계산식은 (2X3X3)이다. 즉 (()
에서 2X2=4라는 값을 계산한 뒤, 닫힌 괄호를 마주했으므로 2로 나누어 tmp를 초기화한다. 그래야 이후 [[]])
를 계산할때 맨처음 열린괄호 (의 값과 함께 계산해 나아갈 수 있다.
위의 설명은 문제의 핵심 포인트 위주로 설명했다면 아래의 설명은 코드 실행 순서대로 다시 정리한 것이다.
arr=input()
stack=[]
answer=0
tmp=1
for i in range(len(arr)):
if arr[i] =='(':
stack.append(arr[i])
tmp *=2
elif arr[i] == '[':
stack.append(arr[i])
tmp *=3
elif arr[i] == ")":
if not stack or stack[-1] == "[":
answer = 0 # 실패
break
if arr[i-1] == "(":
answer += tmp
stack.pop()
tmp //= 2 #tmp 초기화
else:
if not stack or stack[-1] == "(":
answer=0
break
if arr[i-1] =='[':
answer+=tmp
stack.pop()
tmp //=3 #tmp 초기화
if stack:
print(0)
else:
print(answer)
음.. 아무리 쉽게 설명해보려해도 나만 이해할 수 있을 것만 같다..
이해가 쉽도록 글을 짜임새있게 쓰는 것도 대단한 능력인 것 같다
내 기준 이해가 가장 쉬웠던 풀이는 그림과 손글씨가 있는 것이었기에 .. 번거롭더라도 자주 손글씨 풀이를 업로드해야겠다