균형 잡힌 괄호 timer 2s memory 512MB

지홍이는 괄호 ‘(’와 ‘) 문자들을 가지고 노는 것을 좋아한다. 특히 균형 잡힌 괄호 문자열 만들기를 좋아한다.

균형 잡힌 괄호 문자열이라는 것은 다음 특징을 만족하는 경우이다.

1. 문자열 “()”는 균형 잡힌 괄호이다.    

2. 균형 잡힌 괄호 두 개를 이어 붙인 문자열도 균형 잡힌 괄호이다.    

3. 문자열 T가 균형 잡힌 괄호라면 문자열 T양쪽에 ‘(’와 ‘)’를 감싼 문자열도 균형 잡힌 괄호이다.

예를 들어 “()()”나 “(()())”는 균형 잡힌 괄호 문자열이지만 “)(”와 “)()(()”는 균형 잡힌 괄호 문자열이 아니다.

괄호 문자열을 가지고 놀던 지홍이는 다음 특징을 갖는 괄호 문자열을 A지홍 괄호 문자열이라고 이름을 붙였다.    

1. 인접한 문자를 정확히 A번 교환하여 균형 잡힌 괄호 문자열 만들 수 있다.    

2. 인접한 문자를 교환하는데 B( 음이 아닌 정수 B < A)번 교환해서는 균형 잡힌 괄호를 만들 수 없다.    

3. 위 두 조건을 만족하는 가장 짧은 괄호 문자열이다.    

4. 위 세 조건을 만족하는 괄호 문자열이 여러 개 있을 경우 아스키 코드 순으로 가장 빠른 괄호 문자열이다.

여러분이 해야 할 일은 양의 정수 A를 입력받아 A지홍 괄호 문자열을 구하는 것이다.