마법 괄호

LISP 프로그래밍 언어에서는 모든 것이 균형 잡힌 괄호 (LIKE THIS) 안에 작성된다. 그래서 LISP 코드에는 닫는 괄호가 길게 이어지는 구간 )))...)이 나타나기도 한다. 닫는 괄호 )의 개수를 여는 괄호 (의 개수와 정확히 맞추는 일은 번거롭고 실수하기 쉽다.

이러한 오류를 막기 위해 일부 LISP 방언은 마법 닫는 괄호 ]를 도입한다. 이 기호는 현재 열려 있는 괄호를 균형 맞추는 데 필요한 만큼, 하나 이상의 닫는 괄호 )를 대신한다. 그러면 컴파일러는 각 마법 괄호 ]가 실제로 닫는 괄호 )를 몇 개 대신하는지 계산해야 한다.

여는 괄호 (, 닫는 괄호 ), 마법 괄호 ]로 이루어진 문자열이 주어진다. 문자열 전체가 균형을 이루도록, 각 마법 괄호가 닫는 괄호 )를 몇 개 대신하는지 구하여라.

첫째 줄에 두 정수 N과 M이 공백으로 구분되어 주어진다 (0 ≤ N ≤ 10000000, 0 ≤ M ≤ 5000000). N은 괄호 문자열의 길이이고, M은 그 안에 있는 마법 괄호의 개수이다.

둘째 줄부터 길이 N인 괄호 문자열이 주어진다. 이 문자열은 문자 (, ), ]로만 이루어지며, 문자 ]는 정확히 M번 나타난다 (M ≤ N). 가독성을 위해 문자열은 한 줄에 최대 72자씩 여러 줄로 나누어져 주어질 수 있으므로, 줄바꿈을 무시하고 이어 붙여 하나의 문자열로 만든다.

첫째 줄에, 문자열을 균형 맞출 수 있으면 1을, 없으면 0을 출력한다. (예를 들어 마법 괄호 ] 하나만으로 이루어진 문자열은 결코 균형을 맞출 수 없다.)

0을 출력했다면 더 이상 아무것도 출력하지 않는다.

1을 출력했다면 이어서 M개의 줄을 더 출력한다. 각 마법 괄호 ]는 최소한 하나의 닫는 괄호를 대신해야 한다. 이 중 i번째 줄에는 왼쪽에서 i번째 마법 괄호가 대신하는 닫는 괄호 )의 개수 C_i ≥ 1을 출력한다.

같은 문자열을 균형 맞추는 방법이 여러 가지일 수 있다. 그런 경우에는 사전순으로 가장 큰 수열 C_1, C_2, …, C_M을 출력한다. 즉 C_1을 될 수 있는 한 크게, 그다음 C_2를 될 수 있는 한 크게, 이런 식으로 정한다.

길이가 8이고 마법 괄호가 2개인 첫 번째 예시를 생각해 보자. 이를 균형 맞추는 한 가지 방법은 첫 번째 마법 괄호가 닫는 괄호 3개를, 두 번째 마법 괄호가 1개를 대신하도록 하는 것이며, 그러면 문자열은 완전히 균형 잡힌 ((((()))))가 된다. 앞쪽 값을 더 크게 하는 방법을 택하므로, 이 3, 1이 바로 사전순으로 가장 큰 답이다.