괄호의 값 비교

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

• 한 쌍의 괄호로만 이루어진 문자열 ()는 올바른 괄호열이다.
• \(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\)]이면 >

을 출력한다.

riseoj 작성

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