문제
풀이
스택을 활용한 문제이며, 동작 과정에서 괄호값을 계산해야하는 것이 해당 문제의 포인트이다. () 쌍의 값은 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들을 for문을 통해 한개씩 받아온다.
- 열린 괄호인 경우 tmp에 값을 곱하고 스택에 넣는다.
- 닫힌 괄호인 경우, 일단 기본적으로 쌍이 맞는지 확인한다. 스택이 아예 비어있거나 스택의 마지막 값이 짝이 맞지 않다면 answer=0으로 저장한 후 break를 걸어 반복문을 빠져나간다. (6으로 이동)
- 만약 쌍이 맞다면 해당 쌍이 종속형태의 가장 내부의 쌍인지 확인한다. 확인하는 법은 앞서 말했듯 현재 괄호의 바로 직전 괄호(arr[i-1]임. 스택[i-1] 아님 주의)와 짝이 맞는 경우라면(==열린괄호라면) 가장 내부의 쌍이라고 간주할 수 있다. 가장 내부의 쌍이 맞다면 지금까지 계산한 tmp를 answer에 더해준다.
- 스택의 값을 pop하고 tmp를 괄호 유형에 맞게 2나 3으로 나눈다. (계산이 끝난 괄호쌍 값 제거)
- answer를 출력한다. 만약 5번 과정 이후에도 stack이 남아있었다면 이 또한 쌍 자체가 맞지 않은 입력이었으므로 answer=0으로 초기화한 후 출력해야함을 잊지 말자.
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)🦾 깨달은 점
음.. 아무리 쉽게 설명해보려해도 나만 이해할 수 있을 것만 같다..
이해가 쉽도록 글을 짜임새있게 쓰는 것도 대단한 능력인 것 같다
내 기준 이해가 가장 쉬웠던 풀이는 그림과 손글씨가 있는 것이었기에 .. 번거롭더라도 자주 손글씨 풀이를 업로드해야겠다
