Balanced Sequence

• 어떤 괄호문자열 t가 주어졌을때, longest balanced subsequence의 길이가 어떻게 될지 먼저 생각해보자. 최소 개수의 '(' 또는 ')'를 제거해서 올바른 괄호 문자열 (VPS: Valid Parenthesis String)가 되도록 하면 된다.
  • '('=1, ')'=-1로 치환해서 누적합과 합을 생각하자.
  • VPS가 되려면 누적합이 항상 0이상으로 유지되어야 한다. 누적합의 최솟값이 -k일 경우 앞에서부터 k개의 '('를 제외시키면 항상 누적합이 0 이상이 되도록 유지시킬 수 있다.
  • 또한 VPS가 되려면 합이 0이 되어야 한다. 뒤에서부터 합 만큼의 ')'를 제거시키면 합이 0이 된다.
  • 결국 longest balanced subsequence의 길이는, {전체 문자열의 길이} - {합} + {누적합배열의 최솟값}*2 이다.
• 이제 누적합배열의 최솟값이 최대가 되도록 문자열 조각들을 배치하는 문제가 된다.
  • 각 문자열 조각 안에 있는 VPS 부분문자열들은 제거시켜도 누적합배열의 최솟값을 계산하는데 영향을 주지 않는다. 이것들을 모두 지우고 나면 각 문자열 조각은 a개의 ')' 뒤에 b개의 '('이 붙어있는 형태가 된다.
  • 이제 점수가 깎인 뒤 회복되는 아이템들이 주어질때, 점수의 최솟값을 최대화시키는 사용 순서를 찾는 유명한 그리디 문제와 같은 형태가 되었다. 정렬을 통해서 최적 순서를 결정할수 있다. 그때의 누적합 배열의 최솟값을 구해서 위의 식대로 계산하면 답을 구할수 있다. 시간복잡도는 O(nlogn)

"""Solution code for "BOJ 18978. Balanced Sequence".

- Problem link: https://www.acmicpc.net/problem/18978
- Solution link: http://www.teferi.net/ps/problems/boj/18978

Tags: [greedy]
"""

import operator
from teflib import io as tio


@tio.run_n_times
def main():
    _n, s = tio.read_str_lines()

    down, up = [], []
    for s_i in s:
        down_count = up_count = 0
        for c in s_i:
            if c == '(':
                up_count += 1
            else:
                if up_count > 0:
                    up_count -= 1
                else:
                    down_count += 1
        if up_count >= down_count:
            up.append((down_count, up_count))
        else:
            down.append((down_count, up_count))

    up.sort(key=operator.itemgetter(0))
    down.sort(key=operator.itemgetter(1), reverse=True)
    psum = min_psum = 0
    for d, u in up + down:
        psum -= d
        min_psum = min(min_psum, psum)
        psum += u

    answer = sum(len(s_i) for s_i in s) - psum + min_psum * 2
    print(answer)


if __name__ == '__main__':
    main()