시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB | 798 | 118 | 70 | 12.389% |
(
와 )
만으로 이루어진 두 문자열 A, B이 주어진다.
A의 부분 문자열이면서 B의 부분 문자열이고, 올바른 괄호열인 서로 다른 문자열들의 집합을 S(A, B) 라고 하자.
S(A, B)에 원소가 하나 이상 있는지 판별하고, 원소가 있다면 S(A, B)에서 가장 길이가 긴 문자열의 길이를 구하는 프로그램을 작성하라.
하나의 입력 데이터에서 T개의 테스트 케이스를 해결해야 한다.
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
다음 T개의 각 줄에는, 하나의 테스트 케이스를 구성하는 두 문자열 A와 B가 공백 하나씩을 사이로 두고 주어진다.
각각의 테스트 케이스마다, 주어진 순서대로, 한 개의 줄에,
Σ|A|는 하나의 입력에서 주어지는 모든 A들의 길이 합, Σ|B|는 하나의 입력에서 주어지는 모든 B들의 길이 합으로 정의한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 5 | Σ|A| ≤ 100, Σ|B| ≤ 100 |
2 | 13 | Σ|A| ≤ 1 000, Σ|B| ≤ 1 000 |
3 | 23 | Σ|A| ≤ 10 000, Σ|B| ≤ 10 000 |
4 | 17 | A = B |
5 | 42 | 추가 제약 조건 없음. |
3 ()((())) (()((())))() ))(()(((( )())))))( ())) )))))(())
8 2 2
올바른 괄호열의 정의
올바른 괄호열이란 다음과 같이 정의된다.
()
는 올바른 괄호열이다.(
X)
도 올바른 괄호열이다.예를 들어 (()(()))
나 (())()()
는 올바른 괄호열이지만, (()
나 )((()()
은 모두 올바른 괄호열이 아니다.
부분문자열의 정의
길이가 l인 문자열 s와 1 ≤ i ≤ j ≤ l인 두 정수 i와 j에 대해, s[i..j]는 s의 i번째 문자에서부터 j번째 문자까지를 모두 순서대로 포함하는 문자열이며, 이러한 문자열들을 문자열 s의 부분문자열이라고 한다.
예를 들어 s가 ()(()()
이라면, s[1..5]는 (()
이고, s[1..7]은 ()()
이다. 따라서 (()
과 ()()
은 문자열 ()(()()
의 부분문자열이다. 하지만 )()(
은 문자열 ()(()()
의 부분문자열이 아니다.
Olympiad > 한국정보올림피아드 > KOI 2021 2차대회 > 고등부 3번