K번째 괄호 문자열
면접 대비시간 제한0.25초메모리 제한512 MB
길이 N인 올바른 괄호 문자열을 사전순으로 나열했을 때 K번째 문자열을 구하고, 존재하지 않으면 -1을 출력한다.
문제
괄호 문자열은 다음과 같이 정의한다.
- 빈 문자열은 괄호 문자열이다.
- S가 괄호 문자열일 때, (S)도 괄호 문자열이다.
- S와 T가 괄호 문자열이라면, ST도 괄호 문자열이다.
- 모든 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다.
길이가 N인 괄호 문자열 중에 사전순으로 K번째인 문자열을 출력하는 프로그램을 작성하시오. 사전순으로 가장 앞서는 괄호 문자열은 0번째이다. '('가 ')'보다 사전순으로 앞선다.
입력
첫째 줄에 자연수 N과 K가 주어진다.
출력
첫째 줄에 K번째 괄호 문자열을 출력한다. K번째 괄호 문자열이 없는 경우에는 -1을 출력한다.
제한
- 2 ≤ N ≤ 50, N은 짝수
- 0 ≤ K ≤ 2N-1