[BOJ] 33693 - C)

https://www.acmicpc.net/problem/33693

BOJ - C)

문제 유형: 그리디, 문자열

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 1024MB

 

문제

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

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

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

 

입력

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

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

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

 

출력

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

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

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

 

풀이

C는 여는괄호로 쓰면 공짜다. 대신 닫는괄호는 2나 비용이 든다.

U는 어느방향으로 하던, 1의 비용이 든다.

 

즉, C는 되도록 여는괄호로 사용하고, U는 닫는괄호로 쓰려고 하면 맞는다.

만약 이전에 짝이 없는 여는괄호가 하나도 없다면, U는 여는 데 써야 한다. 이를 제외하고 항상 닫는 데 쓴다.

만약 남은 괄호들을 모두 닫는 데 사용해야 한다면, C는 닫는 데 써야 한다. 이를 제외하고 항상 여는 데 쓴다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

void solve() {
    string s;
    cin >> s;

    int stk = 0;
    int ans = 0;
    string anss = "";
    for (int i = 0; i < s.size(); i++) {
        char ch = s[i];
        if (ch == 'U') {
            if (stk == 0) {
                stk++;
                anss += '(';
            } else {
                stk--;
                anss += ')';
            }
            ans++;
        } else {
            if (stk == s.size() - i) {
                stk--;
                ans += 2;
                anss += ')';
            } else {
                stk++;
                anss += '(';
            }
        }
    }

    cout << ans << "\n";
    cout << anss << "\n";
}

int main(int argc, char *argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}