지원 단말 상태 묶음

문제

한 회사의 IT 지원실은 업무용 단말을 관리 번호 순서대로 점검한다. 단말마다 추가 지원이 필요하지 않으면 상태를 0으로, 추가 지원이 필요하면 상태를 1로 기록한다. 점검한 단말 수 N은 1 또는 2의 거듭제곱이다. 지원실은 연속해서 같은 상태가 나타나는 구간을 짧게 기록하기 위해 정해진 묶음 표기법을 사용한다. 어떤 연속 구간의 상태를 표기할 때, 그 구간의 모든 단말이 0이면 문자 0 하나만 적는다. 모든 단말이 1이면 문자 1 하나만 적는다. 구간의 길이가 얼마인지는 이 문자 옆에 따로 적지 않는다. 구간 안에 0과 1이 모두 있으면 구간을 길이가 같은 왼쪽 절반과 오른쪽 절반으로 나눈다. 그런 다음 여는 괄호를 적고, 왼쪽 절반의 표기, 오른쪽 절반의 표기, 닫는 괄호를 순서대로 이어 붙인다. 절반으로 나눈 각 구간에도 똑같은 규칙을 적용한다. 같은 상태로만 이루어진 구간은 더 나누지 않아야 하며, 서로 다른 상태가 섞인 구간은 반드시 절반으로 나누어야 한다. 처음 단말 수가 2의 거듭제곱이므로 나누는 과정에서 두 절반의 길이가 달라지는 일은 없다. 길이가 1인 구간은 언제나 문자 하나로 표기할 수 있다. 예를 들어 상태가 1100인 구간은 왼쪽 절반의 표기가 1이고 오른쪽 절반의 표기가 0이므로 (10)으로 기록한다. 표기 안에는 공백이나 쉼표를 넣지 않으며, 괄호도 규칙에 따라 필요한 것만 적는다. 이 작업에서는 표기의 길이를 임의로 줄이는 다른 방법을 사용하지 않는다. 모든 단말의 상태가 관리 번호 순서대로 주어질 때, 전체 구간에 위 규칙을 적용한 표기를 출력하는 프로그램을 작성한다.

입력

첫째 줄에 단말 수 N이 주어진다. N은 정수이며, 어떤 정수 k에 대하여 N = 2^k이고 0 ≤ k ≤ 16이다.
둘째 줄에 길이가 N인 문자열 S가 주어진다. S는 문자 0과 1로만 이루어져 있으며, 왼쪽부터 관리 번호 순서의 단말 상태를 나타낸다.

출력

전체 단말 구간의 묶음 표기를 한 줄에 출력한다. 표기에는 0, 1, 여는 괄호, 닫는 괄호만 사용하며 공백을 넣지 않는다.

8
00001111

(01)

4
0101

((01)(01))

1
1

1

출처: Devin.KR 자체 제작