시간 제한메모리 제한제출정답맞은 사람정답 비율
4 초 (추가 시간 없음) 1024 MB323865728.079%

문제

여는 괄호 (와 닫는 괄호 )를 이용해서 만들어지는 문자열 중에서 올바른 괄호열이란 다음과 같이 정의 된다.

  • 한 쌍의 괄호로만 이루어진 문자열 ()는 올바른 괄호열이다.
  • X가 올바른 괄호열이면, X를 괄호로 감싼 (X)도 올바른 괄호열이다.
  • X와 Y 가 올바른 괄호열이면, X와 Y 를 이어 붙인 XY도 올바른 괄호열이다.
  • 모든 올바른 괄호열은 위 세 가지 규칙을 통해서만 만들어진다.

예를 들어 (()(()))(())()()는 올바른 괄호열이지만, (())((()()은 모두 올바른 괄호열이 아니다. 우리는 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 f[X]로 표시한다.

  • f[()] = 1
  • X가 올바른 괄호열이면, f[(X)] = 2 × f[X]
  • X와 Y 가 올바른 괄호열이면, f[XY] = f[X] + f[Y ]

예를 들어 몇 가지 올바른 괄호열들의 괄호값을 구해 보자.

  • f[()] = 1
  • f[(())] = 2 × f[()] = 2 × 1 = 2
  • f[()()] = f[()] + f[()] = 1 + 1 = 2
  • f[()()()] = f[()] + f[()()] = 1 + 2 = 3
  • f[(()())] = 2 × f[()()] = 2 × 2 = 4
  • f[((()))] = 2 × f[(())] = 2 × 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개의 테스트 케이스를 해결해야 한다.

입력

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

이후 T개의 테스트 케이스가 차례로 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

  • 첫 번째 줄에 A가 주어진다.
  • 두 번째 줄에 B가 주어진다.

출력

각각의 테스트 케이스마다, 한 개의 줄에,

  • f[A] = f[B]이면 =,
  • f[A] < f[B]이면 <,
  • f[A] > f[B]이면 >

을 출력한다.

제한

  • 1 ≤ T ≤ 10
  • A와 B는 올바른 괄호열이다.
  • 하나의 입력에서 주어지는 모든 테스트 케이스의 A의 길이의 합은 3 000 000 이하이다.
  • 하나의 입력에서 주어지는 모든 테스트 케이스의 B의 길이의 합은 3 000 000 이하이다.

서브태스크

번호 배점 제한
1 3

A의 길이와 B의 길이는 각각 6 이하이다.

2 23

A의 길이와 B의 길이는 각각 50 이하이다.

3 13
  • 여는 괄호와 닫는 괄호의 개수가 같고 모든 닫는 괄호가 모든 여는 괄호의 뒤에 있는 괄호열을 단순 괄호열이라고 하자.
    • 예를 들어 (), (()), ((())), (((((())))))는 단순 괄호열이다.
  • A와 B는 각각 길이가 서로 다른 단순 괄호열 한 개 이상을 이어 붙여 만든 괄호열이다.
    • 예를 들어 ()(()), (((())))()((()))와 같은 문자열이 주어질 수 있다.
    • (())()(())는 단순 괄호열을 이어 붙여 만든 문자열이지만, 길이가 서로 같은 단순 괄호열 (())이 두 번 붙어 있기 때문에, 이 부분문제에서는 주어지지 않는다.
4 61

추가 제약 조건 없음.

예제 입력 1

1
(())
()()

예제 출력 1

=

f[A] = f[(())] = 2이고, f[B] = f[()()] = 2이므로, f[A] = f[B]이다.

예제 입력 2

1
()()()
(()())

예제 출력 2

<

f[A] = f[()()()] = 3이고, f[B] = f[(()())] = 4이므로, f[A] < f[B]이다.

예제 입력 3

2
((()))
()(())
(((())))
()()()()()

예제 출력 3

>
>

첫 번째 테스트 케이스: f[A] = f[((()))] = 4이고, f[B] = f[()(())] = 3이므로, f[A] > f[B]이다.

두 번째 테스트 케이스: f[A] = f[(((())))] = 8이고, f[B] = f[()()()()()] = 5이므로, f[A] > f[B] 이다.

출처

Olympiad > 한국정보올림피아드 > KOI 2021 2차대회 > 초등부 3번

  • 데이터를 추가한 사람: jh05013

채점 및 기타 정보

  • 예제는 채점하지 않는다.