[SWEA] 3950 괄호

출처: [SWEA] SW 문제해결 심화 - 증명의 중요성

 Input 

2

2

)(

10

)))))(((((

 

 Output 

#1 2

1 1

0 0

#2 2

0 4

5 9

※ 첫번째 Test Case와 같이 적용한 연산 순서가 다르더라도 동일한 결과를 가지고 있는 경우가 있는데,

    이 경우 어떤 순서로 해도 상관 없습니다.

 

누적 합 이용하여 문제를 해결할 수 있습니다.

※ 문자열의 길이가 홀수라면 괄호가 유효하지 않습니다.

① 『 ( 』 과 『 ) 』 을 각각 1과 -1로 계산하여 누적합을 구합니다.

    ) ( ( ( ) ( → -1 1 1 1 -1 → 누적합: -1 0 1 2 1

② 누적 합 중 음수이면서 제일 작은 값의 위치 pos를 구합니다.

    존재하지 않는다면 ④단계로 넘어갑니다. 

    (존재한다면 전체 구간의 최솟값에 해당되지만 음수이어야 합니다.)

    (존재하지 않는 경우는 모든 누적합이 양수인 경우)

    

③ 첫번째 위치부터 ②단계에서 찾은  위치 pos까지 연산을 적용합니다.

    ex: ) ( ( ( ) ( → [0, 0] 구간을 뒤집습니다. → ) ( ( ( ) ( → 뒤집은 구간의 괄호의 방향을 반대로 합니다. → ( ( ( ( ) ( 

    연산 결과 누적합을 구해보면 ( ( ( ( ) ( → 1 1 1 1 -1 1 → 누적합: 1 2 3 4 3 4

    모든 누적합들이 양수가 되는 것을 확인할 수 있습니다.

    즉  ②, ③ 단계의 목적은 누적합들을 양수가 되도록 해주는 것입니다.

 

④ 누적합의 마지막 원소가 0인지 확인합니다.

    ( ( ) ) → 1 1 -1 -1 → 누적합: 1 2 1 0 처럼 유효한 괄호쌍인 경우 마지막 누적합이 0일 수 밖에 없습니다.

    마지막 누적합이 0인 아닌 경우 특정 구간에 대해 R 연산처리를 해야 합니다.

     (마지막 원소가 0인 경우 추가 연산 처리 없이 종료)

 

⑤ 누적합의 마지막 원소가 0이 아닌 경우

    마지막 원소의 절반에 해당하는 값을 가지는 누적합들 중 뒤에 위치한 원소를 찾습니다.

 

⑥ 찾은 위치의 다음 괄호부터 마지막 괄호까지 연산 적용합니다.

    ex. ( ( ( ( ) ( → [1, 5] 구간을 뒤집습니다. → ( ( ( ) ( ( → 뒤집은 구간에서 괄호 방향을 바꿉니다. → ( ( ) ( ) )

    ex. ( ( ) ( ( (  → [4, 5] 구간을 뒤집습니다. → ( ( ) ( ( ( → 뒤집은 구간에서 괄호 방향을 바꿉니다. → ( ( ) ( ) )

    결과적으로 누적합의 마지막 결과 = 0이 되면서 유요한 괄호쌍이 되었습니다.

 

* 연산 시도횟수가 최대 10번이라고 했지만 위의 규칙을 이용하면

    문자열의 길이가 홀수인 경우를 제외하고 최대 2번만에 처리할 수 있습니다.

ⅰ. 문자열의 길이가 홀수

    ex. ( ) )

ⅱ. 연산이 두번 필요한 경우 (누적합 중 음수가 존재하는 경우)

      ex. ) ( ( ( ) (

ⅲ. 연산이 한번 필요한 경우 (누적합이 모두 양수이지만 마지막 원소 ≠ 0)

     ex. ( ( ( ( ) (

ⅳ. 연산이 필요 없는 경우(누적합이 모두 양수이면서 마지막 원소 = 0)

    ex.  ( ( ) ( ) ) → 0

 

---

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
 
int flipCnt;
vector<pair<int, int>> result;
vector<int> subSumArr;
 
string rOperation(int left, int right, string str) {
    int s = left, e = right;
    while (left < right) {
        char temp = str[left];
        str[left] = str[right];
        str[right] = temp;
        left++; right--;
    }
 
    for(int i=s; i<=e; i++){
        if (str[i] == '(') str[i] = ')';
        else if (str[i] == ')') str[i] = '(';
    }
 
    return str;
}
 
string flip(string str, int len) {
    int minValue = 0, pos = -1, sum = 0;
    for (int i = 0; i < len; i++) {
        if (str[i] == '(') sum++;
        else if (str[i] == ')') sum--;
 
        if (sum < minValue) {
            minValue = sum; // 음수이면서 제일 작은 값으로 갱신
            pos = i; // 인덱스
        }
    }
 
    // 누적합이 음수인 경우가 존재하였다면
    if (pos != -1) {
        flipCnt++;
        result.push_back(make_pair(0, pos));
        str = rOperation(0, pos, str);
    }
 
    return str;
}
 
void solve(string str, int len) {
    if (len % 2 == 1) {
        flipCnt = -1;
        return;
    }
 
    // 각 구간합 원소가 음수가 없도록 처리
    str = flip(str, len);
 
    // 구간 누적합
    int sum = 0;
    for (int i = 0; i < len; i++) {
        if (str[i] == '(') sum++;
        else if (str[i] == ')') sum--;
        subSumArr.push_back(sum);
    }
 
    if(subSumArr.back() == 0) return;
    
    // 누적합의 절반값을 가지는 누적합들 중 가장 마지막 인덱스 찾기
    int halfValue = subSumArr.back() / 2;
    int pos = -1;
    for (int i = 0; i < len; i++) {
        if (halfValue == subSumArr.at(i)) {
            pos = i + 1;
        }
    }
    result.push_back(make_pair(pos, len - 1));
    flipCnt++;
}
 
int main(void) {
    int testCase;
    cin >> testCase;
    for (int tc = 1; tc <= testCase; tc++) {
        int len; string str;
        cin >> len >> str;
        
        flipCnt = 0;
        subSumArr.clear();
        result.clear();
 
        solve(str, len);
 
        printf("#%d %d\n", tc, flipCnt);
        for (int i = 0; i < result.size(); i++) {
            printf("%d %d\n", result[i].first, result[i].second);
        }
    }
    return 0;
}