BOJ 26137 - Prehistoric Programs 링크
(2024.04.03 기준 P4)

문제

두 괄호((, ))로 이루어진 문자열 $n$개가 주어진다.
$n$개의 문자열을 나열해서 붙였을 때 올바른 괄호 문자열이 되는 임의의 순서 하나 출력

알고리즘

증명이 어려운 그리디 문제

풀이

괄호 문자열 $S$가 올바른 괄호 문자열이 되려면 다음과 같은 두 조건을 만족해야 한다.
1. 모든 $i(1 \le i \le |S|)$에 대해서, 구간 $[1, i]$에서 열린 괄호의 개수가 닫힌 괄호의 개수보다 같거나 많아야 한다.
2. 열린 괄호의 총 개수와 닫힌 괄호의 총 개수는 동일해야 한다.
2번은 판단하기 쉽기 때문에, 우리는 여기서 1번에 집중해야 한다. 결국 열린 괄호를 $1$, 닫힌 괄호를 $-1$이라고 했을 때, 첫 인덱스부터 합을 구하면 어느 인덱스에서라도 음수가 되면 안됨을 뜻한다.

$i$번 문자열의 ((의 개수 - )의 개수)를 $ct_i$라고 하자. 그리고 $tot_i$를 $ct_1$, $\dots$, $ct_i$의 합이라고 하자. $ct_i$가 음수이면 $tot_{i-1}$가 $-ct_i$ 이상이어야 함을 직관적으로 알 수 있다. $tot_i$는 단 한번이라도 음수가 되면 안되기 때문이다. 그러면 일단 $ct_i$가 $0$이거나 양수인 문자열 $i$는 $ct_j$가 음수인 문자열 $j$보다 앞에 와야 함을 탐욕적으로 알 수 있다. 그러니 앞쪽에 배치할 문자열, 뒤쪽에 배치할 문자열을 나눠보자. 올바른 괄호 문자열은 앞쪽부터나 뒤쪽부터나 동일하게 계산할 수 있다. 그러므로 앞쪽에 배치될 문자열은 앞쪽에서부터, 뒤쪽에 배치될 문자열은 뒤쪽에서부터 검사하면 된다.

각 문자열은 사용되기 위해 필요한 괄호의 개수가 정해져 있다. 만약 문자열 $s_i$가 ))((((라면? $ct_i = 2$로 양수지만, 앞쪽에 닫힌 괄호가 $2$개 있기 때문에 반드시 $tot_{i-1}$는 $2$ 이상이어야 한다. 그래야 닫힌 괄호의 개수가 열린 괄호의 개수보다 많아지는 경우가 오지 않는다. 필요한 괄호의 개수는 각각 앞쪽에 배치할 문자열들은 앞에서부터 닫힌 괄호의 개수가 가장 많을 때로, 뒤쪽에 배치할 문자열들은 뒤에서부터 열린 괄호의 개수가 가장 많을 때로 계산하면 된다. 이를 $x_i$라고 하자.

우리는 $x_i$와 $ct_i$를 구했다. 이제 어느 순서로 문자열들을 나열할 것인가 생각해야 한다.

앞쪽에 배치할 문자열부터 살펴보자. $x_i$는 $tot_{i-1}$보다 작아야 한다. 즉, $x$는 오름차순, $ct$는 내림차순으로 정렬해서 나열하면 된다. 이렇게 정렬해서 인덱스 $1$부터 차례대로, $x_i$가 $tot_{i-1}$보다 커지면 불가능한 것으로 판단하면 된다.

뒤쪽에 배치할 문자열을 살펴보자. 여기 포함되어 있는 문자열들을 각각 순서를 뒤집는다면? 앞쪽과 동일한 조건을 갖추게 된다. 그러므로 순서를 뒤집고 앞쪽에 배치할 문자열들을 살펴본 것처럼 동일하게 하자.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef tuple<int, int, int> tiii;

bool comp(tiii a, tiii b){
    if (get<0>(a) == get<0>(b)) return get<1>(a) > get<1>(b);
    return get<0>(a) < get<0>(b);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    /* 올바른 괄호 문자열이 되려면 모든 인덱스에서 닫힌 괄호의 개수가 더 많아지면 안되고
    마지막엔 열린 괄호의 개수와 닫힌 괄호의 개수가 동일해야 한다.

    ('('의 개수) - (')'의 개수)를 ct라고 하자.
    각 문자열마다 ct가 0이나 양수라면 앞쪽에 배치, 음수라면 뒤쪽에 배치되어야 함을 직관적으로 알 수 있다.
    올바른 괄호 문자열은 앞쪽부터나 뒤쪽부터나 동일하게 계산할 수 있다.
    즉 앞쪽에 배치될 문자열은 앞쪽에서부터, 뒤쪽에 배치될 문자열은 뒤쪽에서부터 검사하면 된다.

    각 문자열은 사용되기 위해 필요한 괄호의 개수가 정해져 있다. 왜냐면 ct가 음수가 되지 않아야 하기 때문.
    앞쪽 문자열들은 앞에서부터 닫힌 괄호의 개수가 가장 많을 때로 계산한다.
    뒤쪽 문자열들은 뒤에서부터 열린 괄호의 개수가 가장 많을 때로 계산한다.
    이렇게 계산한 조건을 x라고 하자.

    앞쪽부터 살펴보자.
    x는 오름차순, ct는 내림차순으로 정렬해야 한다. 어떻게든 ct의 합이 단조증가한다.
    그러므로 x는 처음부터 최대한 낮게끔, ct는 그중에서도 최대한 높게 해서 x를 최대한 상쇄시킬 수 있게 해야 한다.
    이렇게 정렬해서 차례대로 살펴보고, x가 현재 ct의 합보다 커지면 불가능한 것이다.

    뒤쪽도 앞쪽과 마찬가지다. 일단 각 ct는 절댓값을 씌우자.
    그러면 앞쪽과 동일하게 조건이 맞춰진다. */

    int n; cin >> n;

    vector<tiii> F, B; // 앞쪽, 뒤쪽
    string s;
    for (int i = 1, ct, ct_, x; i <= n; i++){
        cin >> s;
        ct = 0; // ('('의 개수) - (')'의 개수)
        for (char c: s){
            if (c == '(') ++ct;
            else --ct;
        }

        // 앞쪽에 배치될 문자열. x를 계산하자.
        if (ct >= 0){
            ct_ = 0; // (')'의 개수) - ('('의 개수)
            x = 0;
            for (char c: s){
                if (c == ')') ++ct_;
                else --ct_;
                x = max(x, ct_);
            }
            F.push_back({x, ct, i});
        }

        // 뒤쪽에 배치될 문자열. x를 계산하자.
        else{
            reverse(s.begin(), s.end()); // 뒤에서부터 계산해야 한다.
            ct_ = 0; // ('('의 개수) - (')'의 개수)
            x = 0;
            for (char c: s){
                if (c == '(') ++ct_;
                else --ct_;
                x = max(x, ct_);
            }
            B.push_back({x, -ct, i}); // ct에 절댓값을 씌운다.
        }
    }

    // 앞쪽 살펴보기
    sort(F.begin(), F.end(), comp); // x는 오름차순, ct는 내림차순
    int tot_f = 0; // 앞쪽 ct의 합
    for (auto [x, ct, i]: F){
        if (x > tot_f){ // x가 현재 ct의 합보다 크다면, 닫힌 괄호의 개수가 많아지는 순간이 온다.
            cout << "impossible";
            return 0;
        }
        tot_f += ct;
    }

    // 뒤쪽 살펴보기
    sort(B.begin(), B.end(), comp); // x는 오름차순, ct는 내림차순
    int tot_b = 0; // 뒤쪽 ct의 합
    for (auto [x, ct, i]: B){
        if (x > tot_b){ // x가 현재 ct의 합보다 크다면, 열린 괄호의 개수가 많아지는 순간이 온다.
            cout << "impossible";
            return 0;
        }
        tot_b += ct;
    }

    // 모든 문자열의 (')'의 개수) - ('('의 개수) = 0인지 확인한다.
    if (tot_f - tot_b){
        cout << "impossible";
        return 0;
    }

    // 앞쪽부터 출력한다.
    for (auto [x, ct, i]: F) cout << i << '\n';
    reverse(B.begin(), B.end());
    for (auto [x, ct, i]: B) cout << i << '\n';
}

• Python (PyPy3)

import sys; input = sys.stdin.readline

''' 올바른 괄호 문자열이 되려면 모든 인덱스에서 닫힌 괄호의 개수가 더 많아지면 안되고
마지막엔 열린 괄호의 개수와 닫힌 괄호의 개수가 동일해야 한다.

('('의 개수) - (')'의 개수)를 ct라고 하자.
각 문자열마다 ct가 0이나 양수라면 앞쪽에 배치, 음수라면 뒤쪽에 배치되어야 함을 직관적으로 알 수 있다.
올바른 괄호 문자열은 앞쪽부터나 뒤쪽부터나 동일하게 계산할 수 있다.
즉 앞쪽에 배치될 문자열은 앞쪽에서부터, 뒤쪽에 배치될 문자열은 뒤쪽에서부터 검사하면 된다.

각 문자열은 사용되기 위해 필요한 괄호의 개수가 정해져 있다. 왜냐면 ct가 음수가 되지 않아야 하기 때문.
앞쪽 문자열들은 앞에서부터 닫힌 괄호의 개수가 가장 많을 때로 계산한다.
뒤쪽 문자열들은 뒤에서부터 열린 괄호의 개수가 가장 많을 때로 계산한다.
이렇게 계산한 조건을 x라고 하자.

앞쪽부터 살펴보자.
x는 오름차순, ct는 내림차순으로 정렬해야 한다. 어떻게든 ct의 합이 단조증가한다.
그러므로 x는 처음부터 최대한 낮게끔, ct는 그중에서도 최대한 높게 해서 x를 최대한 상쇄시킬 수 있게 해야 한다.
이렇게 정렬해서 차례대로 살펴보고, x가 현재 ct의 합보다 커지면 불가능한 것이다.

뒤쪽도 앞쪽과 마찬가지다. 일단 각 ct는 절댓값을 씌우자.
그러면 앞쪽과 동일하게 조건이 맞춰진다. '''

n = int(input())

F = []; B = [] # 앞쪽, 뒤쪽
for i in range(1, n + 1):
    s = input().strip()
    ct = 0 # ('('의 개수) - (')'의 개수)
    for c in s:
        if c == '(':
            ct += 1
        else:
            ct -= 1

    # 앞쪽에 배치될 문자열. x를 계산하자.
    if ct >= 0:
        ct_ = 0 # (')'의 개수) - ('('의 개수)
        x = 0
        for c in s:
            if c == ')':
                ct_ += 1
            else:
                ct_ -= 1
            x = max(x, ct_)
        F.append((x, ct, i))

    # 뒤쪽에 배치될 문자열. x를 계산하자.
    else:
        ct_ = 0 # ('('의 개수) - (')'의 개수)
        x = 0
        for c in s[::-1]: # 뒤에서부터 계산해야 한다.
            if c == '(':
                ct_ += 1
            else:
                ct_ -= 1
            x = max(x, ct_)
        B.append((x, -ct, i)) # ct에 절댓값을 씌운다.

# 앞쪽 살펴보기
F.sort(key = lambda x: (x[0], -x[1])) # x는 오름차순, ct는 내림차순
tot_f = 0 # 앞쪽 ct의 합
for x, ct, i in F:
    if x > tot_f: # x가 현재 ct의 합보다 크다면, 닫힌 괄호의 개수가 많아지는 순간이 온다.
        print('impossible')
        exit(0)
    tot_f += ct

# 뒤쪽 살펴보기
B.sort(key = lambda x: (x[0], -x[1])) # x는 오름차순, ct는 내림차순
tot_b = 0 # 뒤쪽 ct의 합
for x, ct, i in B:
    if x > tot_b: # x가 현재 ct의 합보다 크다면, 열린 괄호의 개수가 많아지는 순간이 온다.
        print('impossible')
        exit(0)
    tot_b += ct

# 모든 문자열의 (')'의 개수) - ('('의 개수) = 0인지 확인한다.
if tot_f - tot_b:
    print('impossible')
    exit(0)

# 앞쪽부터 출력한다.
for x, ct, i in F:
    print(i)
for x, ct, i in B[::-1]:
    print(i)