디지털 어니언
시간 제한1초메모리 제한128 MB
균형 잡힌 괄호 문자열이 주어지면 정의된 가격 순서에서 바로 다음 문자열을 출력합니다.
문제
디지털 어니언(Digital Onion, 줄여서 DO)은 괄호로만 이루어진 문자열이다. 다음과 같이 재귀적으로 정의한다.
- 빈 문자열(괄호가 하나도 없는 경우)은 DO이며, 이를 널 DO라고 한다.
()는 DO이며, 이를 기본 DO라고 한다.A와B가 모두 DO이면(A)B도 DO이다. 이때A를 그 DO의 안쪽,B를 바깥쪽이라고 한다.
예를 들어 (())()와 ((()))(()()())는 DO이지만, ()())((와 ((())는 DO가 아니다.
DO의 무게는 그 안에 들어 있는 (의 개수(즉 )의 개수)로 정의한다. 널 DO의 무게는 0, 기본 DO ()의 무게는 1이며, ((()))(()()())의 무게는 7이다.
X = ((()))(()()())이면 X의 안쪽은 (()), 바깥쪽은 (()()())이다. X = (()(()))이면 안쪽은 ()(())이고 바깥쪽은 널 DO이다.
이제 모든 DO에 가격 순서를 다음 세 규칙으로 정한다.
- 규칙 1. 무게가 클수록 더 비싸다.
- 규칙 2. 무게가 같으면 안쪽 DO가 더 비싼 쪽이 더 비싸다.
- 규칙 3. 무게가 같고 안쪽 DO의 가격도 같으면 바깥쪽 DO가 더 비싼 쪽이 더 비싸다.
B가 A보다 비쌀 때 A < B로 쓴다. 예를 들어 규칙 1에 의해 () < (()), (())() < ((()))()이고, 규칙 2에 의해 (())(()) < ((()))()이며, 규칙 3에 의해 (())()() < (())(())이다.
DO X가 주어지면, X보다 비싸면서 그 둘 사이의 가격을 가지는 DO가 존재하지 않는 DO, 즉 다음으로 비싼 DO(NMED, Next More Expensive DO)를 출력하라. 다시 말해 모든 DO를 가격순으로 정렬했을 때 X 바로 다음에 오는 DO이다.
입력
첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에 각각 하나의 DO가 주어진다. 각 줄의 끝은 $로 표시하며, 모든 (, ), 그리고 마지막 $ 사이에는 적어도 하나의 공백이 있다. 입력으로 주어지는 각 DO의 무게는 1 이상 30 이하이다.
출력
각 테스트 케이스마다 한 줄에 다음으로 비싼 DO를 출력하고 그 뒤에 끝 표시 $를 붙인다. 입력과 마찬가지로 모든 (, ), 그리고 $는 하나의 공백으로 구분한다.