괄호 문자열 순서 (라지)
면접 대비시간 제한5초메모리 제한512 MB
n쌍의 올바른 괄호 문자열을 사전 순으로 늘어놓았을 때 k번째 문자열을 출력하고 존재하지 않으면 Doesn't Exist!를 출력합니다.
문제
n쌍 괄호 문자열은 여는 괄호 ( n개와 닫는 괄호 ) n개로 이루어진 길이 2n짜리 문자열이다.
올바른 괄호 문자열은 다음과 같이 정의한다.
서로 붙어 있는 () 한 쌍을 지우는 작업을 반복해서 빈 문자열로 만들 수 있으면 올바른 괄호 문자열이다.
예를 들어 (())는 올바른 괄호 문자열이다. 2번째와 3번째 문자를 지우면 ()가 되고, 한 번 더 지우면 빈 문자열이 된다. )()(는 올바르지 않다. 2번째와 3번째 문자를 지우면 )(가 남고 더는 지울 수 없다.
n쌍 올바른 괄호 문자열을 모두 모아 사전순으로 정렬했을 때 k번째 문자열을 구하여라. 사전순 비교에서 (는 )보다 앞선다.
예를 들어 n이 3일 때 올바른 괄호 문자열을 사전순으로 나열하면 다음과 같다.
((()))
(()())
(())()
()(())
()()()
입력
첫 줄에 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에 각각 두 정수 n과 k가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 n쌍 올바른 괄호 문자열을 사전순으로 정렬했을 때의 k번째 문자열이다. 올바른 괄호 문자열이 k개보다 적으면 y 자리에 Doesn't Exist!를 출력한다.