페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2507

[중등부] 2025 KOI 1차대회 대비 모의고사 (5주차)

C)
스페셜 저지
서브태스크
1초 1024MB

문제

UDPC만을 손꼽아 기다리던 포닉스는 어느새 어디를 봐도 알파벳 U, D, P, C가 보이는 수준에 이르렀다.

그중에서도, 알파벳 C, U와 괄호 ( , )는 굉장히 유사한 모양을 띠기 때문에 구별하기가 매우 힘들어졌다.

다행인 점은, 알파벳 C와 U를 돌려 마치 괄호처럼 사용할 수 있다는 점이다.

C는 그 모습 그대로 여는 괄호 ( 로 사용하거나, 어느 방향으로든 90도씩 두 번을 돌려 닫는 괄호 ) 로 사용할 수 있다.

U는 시계 방향으로 90도를 회전하면 여는 괄호 ( , 반시계 방향으로 90도를 회전하면 닫는 괄호 ) 로 사용할 수 있다.

포닉스는 UDPC를 기다리느라 지쳤기 때문에 알파벳을 최소한으로 돌리고 싶다.

짝수 길이의 C와 U로 이루어진 문자열이 주어지면,

알파벳 중 하나를 골라 어느 방향으로든 90도씩 회전해서 올바른 괄호 문자열을 만들기 위해 필요한 최소 회전 횟수를 구하여라.

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

  • 빈 문자열은 올바른 괄호 문자열이다.

  • S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다.

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


입력

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

둘째 줄부터 T개의 줄에 걸쳐 비어 있지 않은 문자열 S가 주어진다.

S는 길이가 짝수이며, 알파벳 C와 U로만 이루어져 있는 문자열이다.

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


출력

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

각 테스트 케이스에 대해, 둘째 줄에 구성된 괄호 문자열 S'을 출력한다.

S'는 길이가 S와 같고, ( 와 )로 이루어진 올바른 괄호 문자열이어야 한다.

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


부분문제

번호 점수 조건
#110점

1≤T≤5, 모든 테스트 케이스에 대해서 S의 길이의 합은 10 이하이다.

#220점

각 S은 하나의 알파벳으로만 이루어져 있는 문자열이다.

#330점

1≤T≤150, 모든 테스트 케이스에 대해서 S의 길이의 합은 300 이하이다.

#440점

추가 제약 조건 없음


예제 

5
CC
UU
CCUCCUCU
UUUUCCCC
CCUUUUCC
2
()
2
()
5
(())()()
8
()()()()
6
((()))()
로그인해야 코드를 작성할 수 있어요.