C)

시간 제한1초메모리 제한1024 MB

요약
C와 U로 이루어진 문자열을 회전해 올바른 괄호 문자열로 바꿀 때 총 90도 회전 횟수의 최솟값과 결과 문자열을 구한다.
난이도

보통10점 중 6점

유형
그리디, 스택, 문자열
정답자
아직 제출이 없습니다

문제

UDPC만을 손꼽아 기다리던 포닉스는 어느새 어디를 봐도 알파벳 U, D, P, C가 보이는 수준에 이르렀다. 그중에서도, 알파벳 C, U와 괄호 ( , )는 굉장히 유사한 모양을 띠기 때문에 구별하기가 매우 힘들어졌다.

다행인 점은, 알파벳 C와 U를 돌려 마치 괄호처럼 사용할 수 있다는 점이다. C는 그 모습 그대로 여는 괄호 ( 로 사용하거나, 어느 방향으로든 90도씩 두 번을 돌려 닫는 괄호 ) 로 사용할 수 있다. U는 시계 방향으로 90도를 회전하면 여는 괄호 ( , 반시계 방향으로 90도를 회전하면 닫는 괄호 ) 로 사용할 수 있다.

포닉스는 UDPC를 기다리느라 지쳤기 때문에 알파벳을 최소한으로 돌리고 싶다. 짝수 길이의 C와 U로 이루어진 문자열이 주어지면, 알파벳 중 하나를 골라 어느 방향으로든 90도씩 회전해서 올바른 괄호 문자열을 만들기 위해 필요한 최소 회전 횟수를 구하여라.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. (1≤T≤500,000)(1\le T\le 500\\, 000)

둘째 줄부터 TT개의 줄에 걸쳐 비어 있지 않은 문자열 SS가 주어진다. SS는 길이가 짝수이며, 알파벳 C와 U로만 이루어져 있는 문자열이다.

모든 테스트 케이스에 대해서 SS의 길이의 합은 10610^6 이하이다.

출력

각 테스트 케이스에 대해, 첫째 줄에 주어진 문자열 SS를 올바른 괄호 문자열으로 만들기 위해 필요한 최소 회전 횟수를 출력한다.

각 테스트 케이스에 대해, 둘째 줄에 구성된 괄호 문자열 S′S'을 출력한다. S′S'는 길이가 SS와 같고, ( 와 )로 이루어진 올바른 괄호 문자열이어야 한다.

가능한 답이 여러 가지라면 그중 하나만 출력한다.

힌트

올바른 괄호 문자열은 다음과 같이 정의된다.

  • 빈 문자열은 올바른 괄호 문자열이다.
  • S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다.
  • S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 괄호 문자열 ST도 올바른 괄호 문자열이다.

예제1

  1. 예제 1

    입력
    5
CC
UU
CCUCCUCU
UUUUCCCC
CCUUUUCC
    예상 출력
    2
()
2
()
5
(())()()
8
()()()()
6
((()))()