Skip to content
Sign in

괄호의 값 비교

Unrated
한국어

Language

Contribute a translation
Time limit
6000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

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

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

예를 들어 $ \texttt{(()(()))} $나 $ \texttt{(())()()} $는 올바른 괄호열이지만, $ \texttt{(()} $나 $ \texttt{)((()()} $은 모두 올바른 괄호열이 아니다.

우리는 올바른 괄호열 $ X $에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 $ f[X] $로 표시한다.

  • $ f[\texttt{()}]=1 $
  • $ X $가 올바른 괄호열이면, $ f[\texttt{(}X\texttt{)}] = 2 \times f[X] $
  • $ X $와 $ Y $가 올바른 괄호열이면, $ f[XY] = f[X]+f[Y] $

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

  • $ f[\texttt{()}]=1 $
  • $ f[\texttt{(())}]= 2 \times f[\texttt{()}] = 2 \times 1 = 2 $
  • $ f[\texttt{()()}]= f[\texttt{()}] + f[\texttt{()}] = 1 + 1 = 2 $
  • $ f[\texttt{()()()}]= f[\texttt{()}] + f[\texttt{()()}] = 1 + 2 = 3 $
  • $ f[\texttt{(()())}]= 2 \times f[\texttt{()()}] = 2 \times 2 = 4 $
  • $ f[\texttt{((()))}]= 2 \times f[\texttt{(())}] = 2 \times 2 = 4 $
  • $ f[\texttt{()(())}]= f[\texttt{()}] + f[\texttt{(())}] = 1 + 2 = 3 $
  • $ f[\texttt{(()())()(())}]= f[\texttt{(()())}] + f[\texttt{()(())}] = 4 + 3 = 7 $

두 개의 올바른 괄호열 $ A $와 $ B $를 읽고, 두 문자열의 괄호값 $ f[A] $와 $ f[B] $를 비교하는 프로그램을 작성하라.

즉, $ f[A] = f[B] $인지, $ f[A] < f[B] $인지, $ f[A] > f[B] $인지를 판단하는 프로그램을 작성하라.

하나의 입력에서 $ T $개의 테스트 케이스를 해결해야 한다.

Constraints

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

Subtasks

  1. (3점) $ A $의 길이와 $ B $의 길이는 각각 $ 6 $ 이하이다.
  2. (23점) $ A $의 길이와 $ B $의 길이는 각각 $ 50 $ 이하이다.

  3. (13점)

    • 여는 괄호와 닫는 괄호의 개수가 같고 모든 닫는 괄호가 모든 여는 괄호의 뒤에 있는 괄호열을 단순 괄호열이라고 하자.

      • 예를 들어 $ \texttt{()} $, $ \texttt{(())} $, $ \texttt{((()))} $, $ \texttt{(((((())))))} $는 단순 괄호열이다.

      • $ A $와 $ B $는 각각 길이가 서로 다른 단순 괄호열 한 개 이상을 이어 붙여 만든 괄호열이다.

        • 예를 들어 $ \texttt{()(())} $, $ \texttt{(((())))()((()))} $와 같은 문자열이 주어질 수 있다.

          • $ \texttt{(())()(())} $는 단순 괄호열을 이어 붙여 만든 문자열이지만, 길이가 서로 같은 단순 괄호열 $ \texttt{(())} $이 두 번 붙어 있기 때문에, 이 부분문제에서는 주어지지 않는다.
  4. (61점) 추가 제약 조건 없음.

Input

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

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

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

Output

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

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

을 출력한다.

Examples

Sample input 1
1
(())
()()
Sample output 1
=

$ f[A] = f[\texttt{(())}]= 2 $이고, $ f[B] = f[\texttt{()()}]=2 $이므로, $ f[A] = f[B] $이다.

Sample input 2
1
()()()
(()())
Sample output 2
<

$ f[A] = f[\texttt{()()()}]= 3 $이고, $ f[B] = f[\texttt{(()())}]=4 $이므로, $ f[A] < f[B] $이다.

Sample input 3
2
((()))
()(())
(((())))
()()()()()
Sample output 3
>
>

첫 번째 테스트 케이스에 대해 $ f[A] = f[\texttt{((()))}]= 4 $이고, $ f[B] = f[\texttt{()(())}]=3 $이므로, $ f[A] > f[B] $이다. 두 번째 테스트 케이스에 대해 $ f[A] = f[\texttt{(((())))}]= 8 $이고, $ f[B] = f[\texttt{()()()()()}]=5 $이므로, $ f[A] > f[B] $이다.

Tags

No tags yet

Source