레이팅 미적용(와 )만으로 이루어진 두 문자열 \(A\), \(B\)와 자연수 \(K\)가 주어진다.
\(A\)의 부분 문자열이면서 \(B\)의 부분 문자열이고, 올바른 괄호열인 서로 다른 문자열들의 집합을 \(S\)(\(A\), \(B\))라고 하자.
\(S\)(\(A\), \(B\))의 크기가 \(K\) 이상인지 판별하고, 만약 크기가 \(K\) 이상이라면 \(S\)(\(A\), \(B\))를 사전 순으로 정렬했을 때 \(K\)번째 문자열을 구하는 프로그램을 작성하라.
하나의 입력 데이터에서 \(T\)개의 테스트 케이스를 해결해야 한다.
Hint.
올바른 괄호열의 정의
올바른 괄호열이란 다음과 같이 정의된다.
- 한 쌍의 괄호로만 이루어진 문자열
()는 올바른 괄호열이다. - \(X\)가 올바른 괄호열이면, \(X\)를 괄호로 감싼
(\(X\))도 올바른 괄호열이다. - \(X\)와 \(Y\) 가 올바른 괄호열이면, \(X\)와 \(Y\) 를 이어 붙인 XY도 올바른 괄호열이다.
- 모든 올바른 괄호열은 위 세 가지 규칙을 통해서만 만들어진다.
예를 들어 (()(()))나 (())()()는 올바른 괄호열이지만, (()나 )((()()은 모두 올바른 괄호열이 아니다.
부분문자열의 정의
길이가 \(l\)인 문자열 \(s\)와 \(1 \le i \le j \le l\)인 두 정수 \(i\)와 \(j\)에 대해, \(s\)[\(i\)..\(j\)]는 \(s\)의 \(i\)번째 문자에서부터 \(j\)번째 문자까지를 모두 순서대로 포함하는 문자열이며, 이러한 문자열들을 문자열 \(s\)의 부분문자열이라고 한다.
예를 들어 \(s\)가 ()(()()이라면, \(s\)[1..5]는 (()이고, \(s\)[1..7]은 ()()이다. 따라서 (()과 ()()은 문자열 ()(()()의 부분문자열이다. 하지만 )()(은 문자열 ()(()()의 부분문자열이 아니다.
사전 순의 정의
길이가 \(l_{1}\)인 문자열 \(s_{1}\)[1..\(l_{1}\)]이 길이가 \(l_{2}\)인 문자열 \(s_{2}\)[1..\(l_{2}\)]보다 사전 순으로 앞선다는 것은, 아래 두 조건 중 하나가 성립한다는 것과 동치이다.
- \(s_{1}\)이 \(s_{2}\)의 접두사이다. 즉, \(l_{1}\) < \(l_{2}\)이고, 모든 \(1 \le i \le l_{1}\)에 대해 \(s_{1}\)[\(i\)] = \(s_{2}\)[\(i\)]이다.
- \(s_{1}[i] \ne s_{2}[i]\)가 성립하는 가장 작은 \(i\) (\(1 \le i \le min(l_{1},l_{2})\))에 대해 \(s_{1}\)[\(i\)] < \(s_{2}\)[\(i\)]이다.
이 문제에서 여는 괄호 (는 닫는 괄호 )보다 사전에서 앞선 문자이다. 즉 ‘(’ < ‘)’이다.
이 방식은 C++, Java, Python에서 두 문자열을 비교하는 방식과 동일하다.
\(\sum |A|\)는 하나의 입력에서 주어지는 모든 \(A\)들의 길이 합, \(\sum |B|\)는 하나의 입력에서 주어지는 모든 \(B\)들의 길이 합으로 정의한다.
- \(1 \le T \le 500\,000\)
- \(A\)와 \(B\)는 각각 여는 괄호와 닫는 괄호로만 이루어진 길이가 \(1\) 이상인 문자열이다.
- \(1 \le K \le 10^{18}\)
- \(\sum |A| \le 500\,000\)
- \(\sum |B| \le 500\,000\)
첫째 줄에 테스트 케이스의 개수 \(T\)가 주어진다.
다음 \(T\)개의 각 줄에는, 하나의 테스트 케이스를 구성하는 두 문자열 \(A\)와 \(B\)와 자연수 \(K\)가 공백 하나씩을 사이로 두고 주어진다.
각각의 테스트 케이스마다, 주어진 순서대로, 한 개의 줄에,
- \(S\)(\(A\), \(B\))의 크기가 \(K\) 미만이라면, -1을 출력한다.
- \(S\)(\(A\), \(B\))의 크기가 \(K\) 이상이라면, \(S\)(\(A\), \(B\))에서 사전 순 \(K\)번째 문자열을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 4점 | \(\sum |A| \le 100\), \(\sum |B| \le 100\) |
2 | 11점 | \(\sum |A| \le 1\,000\), \(\sum |B| \le 1\,000\) |
3 | 16점 | \(\sum |A| \le 10\,000\), \(\sum |B| \le 10\,000\), \(A = B\), \(K = 1\) |
4 | 25점 | \(\sum |A| \le 10\,000\), \(\sum |B| \le 10\,000\) |
5 | 10점 | \(A = B\), \(K = 1\) |
6 | 12점 | \(A = B\) |
7 | 9점 | \(K = 1\) |
8 | 13점 | 추가 제약 조건 없음. |
3
()((())) (()((())))() 3
))(()(((( )())))))( 1
())) )))))(()) 4
()
()
-1
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2021 > 2차 대회 > 중등부 4번