defis_correct(src):
left = 0; right = 0# 반대괄호가 먼저나온다면 잘못된 괄호문자열if src[0] == ')':
returnFalseelse:
# 왼쪽일경우
left = left + 1for i in src:
# 오른쪽괄호가 왼쪽보다 많아지는순간이 있는경우 잘못된괄호문자열if left < right:
returnFalseelif i == '(':
left = left + 1elif i == ')':
right = right + 1# 이상없을시 올바른 괄호문자열returnTruedefcorrection(src):# 1. 입력이 빈 문자열iflen(src) == 0:
return''# index 설정
idx = 0; left = 0; right = 0for i inrange(len(src)):
# 균형잡힌 문자열 체크if src[i] is'(':
left = left + 1elif src[i] is')':
right = right + 1# 균형잡힌만큼 index 를 저장if left == right:
idx = i + 1break# 2. u와 v로 분리
u = src[0:idx]; v = src[idx:]
# 3. u가 올바른 문자열이면 v에 대해 recursiveif is_correct(u):
# 3-1 수행한 결과 문자열을 u에 이어붙인후 반환return u + correction(v)
# 4. u 가 올바르지 않다면else:
# 4-1 ~ 4-3 빈문자열에 ( 추가후 v계산후에 )붙여넣기
tmp = '(' + correction(v) + ')'# 4-4 나머지 문자열 뒤집기for i inrange(1, len(u) - 1):
if u[i] is'(':
tmp = tmp + ')'else:
tmp = tmp + '('return tmp
defsolution(p):return correction(p)