괄호의 값 비교
골드 II의견: 0
여는 괄호 (와 닫는 괄호 )를 이용해서 만들어지는 문자열 중에서 올바른 괄호열이란 다음과 같이 정의 된다.
- 한 쌍의 괄호로만 이루어진 문자열
()는 올바른 괄호열이다. - X가 올바른 괄호열이면, X를 괄호로 감싼
(X)도 올바른 괄호열이다. - X와 Y 가 올바른 괄호열이면, X와 Y 를 이어 붙인 XY도 올바른 괄호열이다.
- 모든 올바른 괄호열은 위 세 가지 규칙을 통해서만 만들어진다.
예를 들어 (()(()))나 (())()()는 올바른 괄호열이지만, (()나 )((()()은 모두 올바른 괄호열이 아니다. 우리는 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 f[X]로 표시한다.
- f[
()] = 1 - X가 올바른 괄호열이면, f[(X)] = \(2 \times f\)[X]
- X와 Y 가 올바른 괄호열이면, f[XY] = f[X] + f[Y ]
예를 들어 몇 가지 올바른 괄호열들의 괄호값을 구해 보자.
- f[
()] = 1 - f[
(())] = \(2 \times f\)[()] = \(2 \times 1 = 2\) - f[
()()] = f[()] + f[()] = 1 + \(1 = 2\) - f[
()()()] = f[()] + f[()()] = 1 + \(2 = 3\) - f[
(()())] = \(2 \times f\)[()()] = \(2 \times 2 = 4\) - f[
((()))] = \(2 \times f\)[(())] = \(2 \times 2 = 4\) - f[
()(())] = f[()] + f[(())] = 1 + \(2 = 3\) - f[
(()())()(())] = f[(()())] + f[()(())] = 4 + \(3 = 7\)
두 개의 올바른 괄호열 A와 B를 읽고, 두 문자열의 괄호값 f[A]와 f[B]를 비교하는 프로그램을 작성하라. 즉, f[A] = f[B]인지, f[A] < f[B]인지, f[A] > f[B]인지를 판단하는 프로그램을 작성하라.
하나의 입력에서 T개의 테스트 케이스를 해결해야 한다.
- \(1 \le T \le 10\)
- \(A\)와 \(B\)는 올바른 괄호열이다.
- 하나의 입력에서 주어지는 모든 테스트 케이스의 \(A\)의 길이의 합은 \(3\,000\,000\) 이하이다.
- 하나의 입력에서 주어지는 모든 테스트 케이스의 \(B\)의 길이의 합은 \(3\,000\,000\) 이하이다.
첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.
이후 T개의 테스트 케이스가 차례로 주어진다. 각 테스트 케이스의 형식은 다음과 같다.
- 첫 번째 줄에 A가 주어진다.
- 두 번째 줄에 B가 주어진다.
각각의 테스트 케이스마다, 한 개의 줄에,
- f[A] = f[B]이면
=, - f[A] < f[B]이면
<, - f[A] > f[B]이면
>
을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 3점 | \(A\)의 길이와 \(B\)의 길이는 각각 \(6\) 이하이다. |
2 | 23점 | \(A\)의 길이와 \(B\)의 길이는 각각 \(50\) 이하이다. |
3 | 13점 | 여는 괄호와 닫는 괄호의 개수가 같고 모든 닫는 괄호가 모든 여는 괄호의 뒤에 있는 괄호열을 단순 괄호열이라고 하자. 예를 들어 |
4 | 61점 | 추가 제약 조건 없음. |
1
(())
()()
=
1
()()()
(()())
<
2
((()))
()(())
(((())))
()()()()()
>
>
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2021 > 2차 대회 > 초등부 3번
평가 및 의견
괄호의 값 비교
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
괄호의 값 비교