14056번 - K번째 좋은 문자열

좋은 문자열은 다음과 같이 정의된다.

• 문자열 "()"는 좋은 문자열이다.
• S가 좋은 문자열 이라면, "(SS...S)"도 좋은 문자열이다. 즉, 좋은 문자열 하나를 여러개 연속해서 놓은 다음, 괄호로 감싼 것이 좋은 문자열이다.
• 위의 두 경우를 제외하면 좋은 문자열은 없다.

문자열 X의 부분 수열은 X에서 0개 이상의 문자를 지워서 얻을 수 있다.

문자열 S가 주어진다. S의 각 문자는 '(' 또는 ')' 이다.

G를 S의 부분 수열 중에서 서로 다른 좋은 문자열인 것의 집합이라고 하자. 즉, 같은 좋은 문자열이 여러 번 나온다고 해도, 집합이기 때문에 G에는 하나만 들어있게 된다. 예를 들어, S = "(()())"인 경우에 G에는 "()", "(())", "(()())"이 들어있게 된다.

K가 주어졌을 때, G에 들어있는 문자열 중에서 사전 순으로 K번째인 것을 찾는 프로그램을 작성하시오. 인덱스는 1부터 시작한다.

첫째 줄에 문자열 S와 정수 K가 주어진다. S의 길이는 150보다 작거나 같은 자연수이고, K는 1보다 크거나 같고, 10⁹보다 작거나 같은 자연수이다.

첫째 줄에 G에 들어있는 문자열 중에서 사전 순으로 K번째 작은 문자열을 출력한다. 만약, 그러한 문자열이 없는 경우에는 -1을 출력한다.