KOI 2차 2021 중4- 공통 괄호 문자열 사전 > 문제은행 : 정보올림피아드&알고리즘


4805 : 공통 괄호 문자열 사전

제한시간
5000 ms   
메모리제한
1024 MB   
해결횟수
1 회   
시도횟수
4 회   

문제

공통 괄호 문자열 사전

  (와 )만으로 이루어진 두 문자열 A, B와 자연수 K가 주어진다.

  A의 부분 문자열이면서 B의 부분 문자열이고, 올바른 괄호열인 서로 다른 문자열들의 집합을 S(A, B)라고 하자.

  S(A, B)의 크기가 K 이상인지 판별하고, 만약 크기가 K 이상이라면 S(A, B)를 사전 순으로 정렬했을 때

K번째 문자열을 구하는 프로그램을 작성하라.

 하나의 입력 데이터에서 T개의 테스트 케이스를 해결해야 한다.

 

참고

  올바른 괄호열의 정의

올바른 괄호열이란 다음과 같이 정의된다.

• 한 쌍의 괄호로만 이루어진 문자열 ()는 올바른 괄호열이다.

• X가 올바른 괄호열이면, X를 괄호로 감싼 (X)도 올바른 괄호열이다.

• X와 Y 가 올바른 괄호열이면, X와 Y 를 이어 붙인 XY 도 올바른 괄호열이다.

• 모든 올바른 괄호열은 위 세 가지 규칙을 통해서만 만들어진다.

예를 들어 (()(()))나 (())()()는 올바른 괄호열이지만, (()나 )((()()은 모두 올바른 괄호열이 아니다.

 

  부분문자열의 정의

  길이가 l​ 인 문자열 s와 1 ≤ i ≤ j ≤ 인 두 정수 i와 j에 대해, s[i..j]는 s의 i번째 문자에서부터 j번째

문자까지를 모두 순서대로 포함하는 문자열이며, 이러한 문자열들을 문자열 s의 부분문자열이라고 한다.

  예를 들어 s가 ()(()()이라면, s[3..5]는 (()이고, s[4..7]은 ()()이다. 따라서 (()과 ()()은 문자열

()(()()의 부분문자열이다. 하지만 )()(은 문자열 ()(()()의 부분문자열이 아니다.

 

  사전 순의 정의

  길이가 l1인 문자열 s1[1..l​1]이 길이가 l2인 문자열 s2[1..l2]보다 사전 순으로 앞선다는 것은, 

아래 두 조건 중 하나가 성립한다는 것과 동치이다.

• s1이 s2의 접두사이다. 즉, l1 < l2이고, 모든 1 ≤ i ≤ l1에 대해 s1[i] = s2[i]이다.

• s1[i] ≠ s2[i]가 성립하는 가장 작은 i (1 ≤ i ≤ min(l1, l2))에 대해 s1[i] < s2[i]이다.

  이 문제에서 여는 괄호 (는 닫는 괄호 )보다 사전에서 앞선 문자이다. 즉 ‘(’ < ‘)’이다.

  이 방식은 C++, Java, Python에서 두 문자열을 비교하는 방식과 동일하다.

제약 조건

 ∑|A|는 하나의 입력에서 주어지는 모든 A들의 길이 합,

 ∑|B|는 하나의 입력에서 주어지는 모든 B들의 길이 합으로 정의한다.

 

• 1 ≤ T ≤ 500 000

• A와 B는 각각 여는 괄호와 닫는 괄호로만 이루어진 길이가 1 이상인 문자열이다.

• 1 ≤ K ≤ 1018

• |A| ≤ 500 000

• |B| ≤ 500 000

 

부분문제

1. (4점) |A| ≤ 100, |B| ≤ 100

2. (11점) |A| ≤ 1 000, |B| ≤ 1 000

3. (16점) |A| ≤ 10 000, |B| ≤ 10 000, A = B, K = 1

4. (25점) |A| ≤ 10 000, |B| ≤ 10 000

5. (10점) A = B, K = 1

6. (12점) A = B

7. (9점) K = 1

8. (13점) 추가 제약 조건 없음. 


입력형식

  첫째 줄에 테스트 케이스의 개수 T가 주어진다. 

  다음 T개의 각 줄에는, 하나의 테스트 케이스를 구성하는 두 문자열 

A와 B와 자연수 K가 공백 하나씩을 사이로 두고 주어진다. 


출력형식

각각의 테스트 케이스마다, 주어진 순서대로, 한 개의 줄에, 

• S(A, B)의 크기가 K 미만이라면, -1을 출력한다. 

• S(A, B)의 크기가 K 이상이라면, S(A, B)에서 사전 순 K번째 문자열을 출력한다.  


입력 예

3
()((())) (()((())))() 3
))(()(((( )())))))( 1
())) )))))(()) 4

출력 예

()
()
-1


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP