33693번 - C) 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 218 | 151 | 115 | 66.860% |
문제
UDPC만을 손꼽아 기다리던 포닉스는 어느새 어디를 봐도 알파벳 U, D, P, C가 보이는 수준에 이르렀다. 그중에서도, 알파벳 C, U와 괄호 ( , )는 굉장히 유사한 모양을 띠기 때문에 구별하기가 매우 힘들어졌다.
다행인 점은, 알파벳 C와 U를 돌려 마치 괄호처럼 사용할 수 있다는 점이다. C는 그 모습 그대로 여는 괄호 ( 로 사용하거나, 어느 방향으로든 90도씩 두 번을 돌려 닫는 괄호 ) 로 사용할 수 있다. U는 시계 방향으로 90도를 회전하면 여는 괄호 ( , 반시계 방향으로 90도를 회전하면 닫는 괄호 ) 로 사용할 수 있다.
포닉스는 UDPC를 기다리느라 지쳤기 때문에 알파벳을 최소한으로 돌리고 싶다. 짝수 길이의 C와 U로 이루어진 문자열이 주어지면, 알파벳 중 하나를 골라 어느 방향으로든 90도씩 회전해서 올바른 괄호 문자열을 만들기 위해 필요한 최소 회전 횟수를 구하여라.
입력
첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\le T\le 500\, 000)$
둘째 줄부터 $T$개의 줄에 걸쳐 비어 있지 않은 문자열 $S$가 주어진다. $S$는 길이가 짝수이며, 알파벳 C와 U로만 이루어져 있는 문자열이다.
모든 테스트 케이스에 대해서 $S$의 길이의 합은 $10^6$ 이하이다.
출력
각 테스트 케이스에 대해, 첫째 줄에 주어진 문자열 $S$를 올바른 괄호 문자열으로 만들기 위해 필요한 최소 회전 횟수를 출력한다.
각 테스트 케이스에 대해, 둘째 줄에 구성된 괄호 문자열 $S'$을 출력한다. $S'$는 길이가 $S$와 같고, ( 와 )로 이루어진 올바른 괄호 문자열이어야 한다.
가능한 답이 여러 가지라면 그중 하나만 출력한다.
예제 입력 1
5 CC UU CCUCCUCU UUUUCCCC CCUUUUCC
예제 출력 1
2 () 2 () 5 (())()() 8 ()()()() 6 ((()))()
노트
올바른 괄호 문자열은 다음과 같이 정의된다.
- 빈 문자열은 올바른 괄호 문자열이다.
S가 올바른 괄호 문자열이라면,(S)도 올바른 괄호 문자열이다.S와T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 괄호 문자열ST도 올바른 괄호 문자열이다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호