def is_correct(src):
left = 0; right = 0
# 반대괄호가 먼저나온다면 잘못된 괄호문자열
if src[0] == ')':
return False
else:
# 왼쪽일경우
left = left + 1
for i in src:
# 오른쪽괄호가 왼쪽보다 많아지는순간이 있는경우 잘못된괄호문자열
if left < right:
return False
elif i == '(':
left = left + 1
elif i == ')':
right = right + 1
# 이상없을시 올바른 괄호문자열
return True
def correction(src):
# 1. 입력이 빈 문자열
if len(src) == 0:
return ''
# index 설정
idx = 0; left = 0; right = 0
for i in range(len(src)):
# 균형잡힌 문자열 체크
if src[i] is '(':
left = left + 1
elif src[i] is ')':
right = right + 1
# 균형잡힌만큼 index 를 저장
if left == right:
idx = i + 1
break
# 2. u와 v로 분리
u = src[0:idx]; v = src[idx:]
# 3. u가 올바른 문자열이면 v에 대해 recursive
if 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 in range(1, len(u) - 1):
if u[i] is '(':
tmp = tmp + ')'
else:
tmp = tmp + '('
return tmp
def solution(p):
return correction(p)
src = input()
dst = src
# 가능한 step수들을 탐색
for step in range(1, len(src)//2+1):
# 비교하기전에 넣어둘 list 선언
tmp = ''
# step 만큼 이동하며 문자열 압축이가능한지확인
i = 0
while i < len(src):
# 압축이 가능할 경우
if src[i:i+step] == src[i+step:i+2*step]:
compress = 2
# 다음스텝으로
i = i + step
# compress 가능한 문자열 체크
for j in range(i, len(src), step):
if src[j:j+step] == src[j+step:j+2*step]:
# 있다면 숫자를 추가한뒤에 다음스텝으로
compress = compress + 1
i = i + step
else:
# 없다면 중지
break
# 문자열 연산을통해 문자열 생성
tmp = tmp + str(compress) + src[j:j+step]
# 다음스텝으로
i = i + step
# 압축이 불가할경우
else:
# step 만큼 list에 넣고 다음 step으로 이동
tmp = tmp + src[i:i+step]
i = i + step
# 압축이완료될경우 기존의 압축과 압축률비교a
if len(tmp) < len(dst):
# 압축률이 좋을경우 대체
dst = tmp
print(dst)
