https://www.acmicpc.net/problem/2504
문제 해결 방법
1. 괄호가 정상적인지 확인한다.
2. 스택을 만들고, 괄호열의 값을 계산하기 위한 변수를 선언한다. (변수의 초깃값은 1)
3. 여는 괄호일 경우, 변수에 괄호의 종류에 따라 2혹은 3을 곱한다.
4. 닫는 괄호가 나올경우, 그 이후 또다른 여는 괄호가 나올 때까지 닫는 괄호가 나올 수 있다.
(여는 괄호가 나오지 않는다면 결국 모든 괄호열의 순회를 완료하게 됨)
단, 괄호를 연만큼 닫는 괄호가 나오지만, 괄호가 닫히지 않은 경우는 계속 나머지 값들에 영향을 줘야만 한다.
따라서, 괄호가 닫히는 경우 나머지 값들에 영향을 주지 않기 위해 괄호의 종류에 따라 2 혹은 3으로 나눈다.
5. 3-4를 괄호열 순회를 마칠 때 까지 수행한다.
6. 결과값을 출력한다.
코드 구현
정답 코드
s = input()
stack=[]
check = 0
for i in s:
if i =='(':
stack.append('(')
elif i == '[':
stack.append('[')
elif i == ')':
if stack:
if stack[-1]=='(':
stack.pop()
else:
check = 1
print(0)
break
else:
check = 1
print(0)
break
elif i == ']':
if stack:
if stack[-1]=='[':
stack.pop()
else:
check = 1
print(0)
break
else:
check =1
print(0)
break
if check == 0:
if stack:
print(0)
else:
checkingStack = []
result=0
tmpV=1
for index, j in enumerate(s):
if j=='(':
tmpV*=2
check =1
checkingStack.append('(')
elif j=='[':
tmpV*=3
check =1
checkingStack.append('[')
elif j==')':
if check ==1: # 최초로 닫는괄호
result+=tmpV
tmpV=tmpV//2
check=0
checkingStack.pop()
else:
tmpV=tmpV//2
checkingStack.pop()
elif j==']':
if check ==1: # 최초로 닫는괄호
result+=tmpV
tmpV=tmpV//3
check=0
checkingStack.pop()
else:
tmpV=tmpV//3
checkingStack.pop()
#print('checkingStack', checkingStack, ' result: ', result, 'index: ', index, ' tmpV: ', tmpV)
print(result)
시간/공간 복잡도
해당 문제는 구현문제이기 때문에 시간/공간 복잡도를 따지지 않는다.
최적화 및 개선
따로 하지 않음
어려웠던 점
문제를 풀다보면 결국 관건은 괄호를 닫을때 지금까지 계산한 값을 곱셈( (X) 혹은 [X] )을 할 것이냐 덧셈(결합)을 할 것이냐를 구분하는 것이 어렵다. 그런데 어떤식으로 하든 해결할 방법이 생각나지 않았다.
(후위 계산인가 싶어서 별거 다해봄)
결과적으로는 분배법칙의 아이디어를 통해 해당 문제를 해결했다.
( ( ) [ [ ] ] ) 해당 괄호의 경우, 분배법칙을 적용하면 ...
( ( ) ) ( [ [ ] ] ) 이렇게 풀 수 있다.
두 괄호는 계산해보면 결과 값이 같다.
이를 잘 고려하여, 계산을 위한 변수 값을 잘 다루어 문제를 해결할 수 있었다.
흔적 (보지마세요)
더보기
# 괄호열이 뭔지?
# 올바른 괄호열인지 체크 = 쌍을 이루는지 체크
# 닫기를 시작했을때, 계산시작
# () = 2, [] = 3
# 다 닫고(if stack:) 새로 열때 +
s = input()
stack=[]
check = 0
for i in s:
if i =='(':
stack.append('(')
elif i == '[':
stack.append('[')
elif i == ')':
if stack:
if stack[-1]=='(':
stack.pop()
else:
check = 1
print(0)
break
else:
check = 1
print(0)
break
elif i == ']':
if stack:
if stack[-1]=='[':
stack.pop()
else:
check = 1
print(0)
break
else:
check =1
print(0)
break
if check == 0:
if stack:
print(0)
else:
print('좋다 시작하자 ')
checkingStack = []
cal=''
result = 0
for index, j in enumerate(s):
if j=='(':
if not checkingStack:
cal+='(2*'
checkingStack.append(j)
else:
if checkingStack[-1]=='(':
cal+='((2+'
checkingStack.append(j)
elif checkingStack[-1]=='[':
cal+='(2#'
checkingStack.append(j)
elif checkingStack[-1]==')' or checkingStack[-1]==']':
cal+='+(2$'
checkingStack.append(j)
elif j=='[':
if not checkingStack:
cal+='(3'
checkingStack.append(j)
else:
if checkingStack[-1]=='[':
cal+='*3'
checkingStack.append(j)
elif checkingStack[-1]=='(':
cal+='(3'
checkingStack.append(j)
elif checkingStack[-1]==']' or checkingStack[-1]==')':
cal+='+(3'
checkingStack.append(j)
elif j==')':
if checkingStack[-1]=='(':
cal+=')'
result= result+(result*2)
checkingStack.pop()
elif j==']':
if checkingStack[-1]=='[':
cal+=')'
result*=3
checkingStack.pop()
print('')
print('j: ', j)
print('checkingStack', checkingStack, ' result: ', result)
print('cal',cal)
check = 0
# # + 추가 작업 // replace, find 다시 공부하기
# while 1:
# check = 0
# result1 = s.find(")(")
# result2 = s.find("][")
# result3 = s.find(")[")
# result4 = s.find("](")
# if result1!=-1:
# s=s.replace(")(", ")+(")
# check =1
# elif result2!=-1:
# s=s.replace("][", "]+[")
# check =1
# elif result3!=-1:
# s=s.replace(")[", ")+[")
# check =1
# elif result4!=-1:
# s=s.replace("](", "]+(")
# check =1
# if check == 0:
# break
# print('result:', s)
# # 2, 3 교체 작업
# while 1:
# check = 0
# result1 = s.find("()")
# result2 = s.find("[]")
# if result1!=-1:
# s=s.replace("()", "2")
# check =1
# elif result2!=-1:
# s=s.replace("[]", "3")
# check =1
# if check == 0:
# break
# print('result?:', s)
# tmpStack=[]
# for i in s:
# tmpStack.append(i)
# print('tmpStack', tmpStack)
# p=[]
# result = 0# 괄호열이 뭔지?
# 올바른 괄호열인지 체크 = 쌍을 이루는지 체크
# 닫기를 시작했을때, 계산시작
# () = 2, [] = 3
# 다 닫고(if stack:) 새로 열때 +
from collections import deque
s = input()
stack=[]
check = 0
for i in s:
if i =='(':
stack.append('(')
elif i == '[':
stack.append('[')
elif i == ')':
if stack:
if stack[-1]=='(':
stack.pop()
else:
check = 1
print(0)
break
else:
check = 1
print(0)
break
elif i == ']':
if stack:
if stack[-1]=='[':
stack.pop()
else:
check = 1
print(0)
break
else:
check =1
print(0)
break
if check == 0:
if stack:
print(0)
else:
#print('좋다 시작하자 ')
calStack=deque([])
checkingStack = []
cal=''
result = 0
for index, j in enumerate(s):
if j=='(' or j=='[':
if index==0:
calStack.append(0)
checkingStack.append(j)
else:
if s[index-1]==')' or s[index-1]==']':
checkingStack.append(j)
# print('된건가?')
elif s[index-1]=='(' or s[index-1]=='[':
checkingStack.append(j)
else:
checkingStack.append(j)
if calStack:
result = calStack[-1]
calStack.clear()
if j==')':
if s[index-1]=='(':
if checkingStack[-1]=='(':
print("들어오긴해?", index)
if index-2>=0:
if s[index-2]==')'or s[index-2]==']':
calStack[-1]+=2
print("나왔어?")
else:
if calStack[-1]==0:
calStack[-1]+=2
checkingStack.pop()
print("!")
else:
calStack[-1]*=2
checkingStack.pop()
print("!!")
elif index-1>=0:
calStack[-1]+=2
print("*")
else:
calStack.append(2)
result+=calStack[-1]
calStack.clear()
checkingStack.pop()
print("@")
elif s[index-1]==')':
if calStack:
if len(checkingStack)==1:
v=sum(calStack)*2
calStack.clear()
calStack.append(v)
else:
calStack[-1]=calStack[-1]*2
checkingStack.pop()
print("??????????")
else:
result=result*2
checkingStack.pop()
print("#")
elif s[index-1]==']':
if checkingStack[-1]=='(':
calStack[-1]=calStack[-1]*2
# result += sum(calStack)*2
# calStack.clear()
# checkingStack.pop()
print('?뭘까???')
if j==']':
if s[index-1]=='[':
if checkingStack[-1]=='[':
if index-2>=0:
if s[index-2]==')'or s[index-2]==']':
calStack[-1]+=3
# print("나왔어?")
else:
if calStack[-1]==0:
calStack[-1]+=3
checkingStack.pop()
else:
calStack[-1]*=3
checkingStack.pop()
elif index-1>=0:
calStack[-1]+=3
# print("!")
else:
calStack.append(3)
result+=calStack[-1]
calStack.clear()
checkingStack.pop()
elif s[index-1]==']':
if calStack:
if len(checkingStack)==1:
v=sum(calStack)*3
calStack.clear()
calStack.append(v)
else:
calStack[-1]=calStack[-1]*3
checkingStack.pop()
# print("?")
else:
result=result*3
checkingStack.pop()
#print('?뭘까')
elif s[index-1]==')':
if checkingStack[-1]=='[':
# result += sum(calStack)*3
# calStack.clear()
# checkingStack.pop()
calStack[-1]=calStack[-1]*3
print('checkingStack', checkingStack, ' result: ', result, ' calStack: ', calStack, 'index: ', index, ' j: ', j)
for i in calStack:
result+=i
print(result)
알게된 것
해당 문제에 대한 접근법
'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글
| [백준9252] LCS 2 (0) | 2024.08.14 |
|---|---|
| [백준17829] 222-풀링 (0) | 2024.08.14 |
| [백준10799] 쇠막대기 (0) | 2024.08.09 |
| [백준2110] 공유기 설치 (0) | 2024.08.06 |
| [백준16918] 봄버맨 (0) | 2024.08.05 |