시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 (추가 시간 없음) | 1024 MB | 217 | 48 | 25 | 20.661% |
(
와 )
만으로 이루어진 두 문자열 A, B와 자연수 K가 주어진다.
A의 부분 문자열이면서 B의 부분 문자열이고, 올바른 괄호열인 서로 다른 문자열들의 집합을 S(A, B)라고 하자.
S(A, B)의 크기가 K 이상인지 판별하고, 만약 크기가 K 이상이라면 S(A, B)를 사전 순으로 정렬했을 때 K번째 문자열을 구하는 프로그램을 작성하라.
하나의 입력 데이터에서 T개의 테스트 케이스를 해결해야 한다.
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
다음 T개의 각 줄에는, 하나의 테스트 케이스를 구성하는 두 문자열 A와 B와 자연수 K가 공백 하나씩을 사이로 두고 주어진다.
각각의 테스트 케이스마다, 주어진 순서대로, 한 개의 줄에,
∑|A|는 하나의 입력에서 주어지는 모든 A들의 길이 합, ∑|B|는 하나의 입력에서 주어지는 모든 B들의 길이 합으로 정의한다.
번호 | 배점 | 제한 |
---|---|---|
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 | 추가 제약 조건 없음. |
3 ()((())) (()((())))() 3 ))(()(((( )())))))( 1 ())) )))))(()) 4
() () -1
올바른 괄호열의 정의
올바른 괄호열이란 다음과 같이 정의된다.
()
는 올바른 괄호열이다.(
X)
도 올바른 괄호열이다.예를 들어 (()(()))
나 (())()()
는 올바른 괄호열이지만, (()
나 )((()()
은 모두 올바른 괄호열이 아니다.
부분문자열의 정의
길이가 l인 문자열 s와 1 ≤ i ≤ j ≤ l인 두 정수 i와 j에 대해, s[i..j]는 s의 i번째 문자에서부터 j번째 문자까지를 모두 순서대로 포함하는 문자열이며, 이러한 문자열들을 문자열 s의 부분문자열이라고 한다.
예를 들어 s가 ()(()()
이라면, s[1..5]는 (()
이고, s[1..7]은 ()()
이다. 따라서 (()
과 ()()
은 문자열 ()(()()
의 부분문자열이다. 하지만 )()(
은 문자열 ()(()()
의 부분문자열이 아니다.
사전 순의 정의
길이가 l1인 문자열 s1[1..l1]이 길이가 l2인 문자열 s2[1..l2]보다 사전 순으로 앞선다는 것은, 아래 두 조건 중 하나가 성립한다는 것과 동치이다.
이 문제에서 여는 괄호 (
는 닫는 괄호 )
보다 사전에서 앞선 문자이다. 즉 ‘(
’ < ‘)
’이다.
이 방식은 C++, Java, Python에서 두 문자열을 비교하는 방식과 동일하다.
Olympiad > 한국정보올림피아드 > KOI 2021 2차대회 > 중등부 4번