중첩 깊이 timer 20s memory 1024MB

tl;dr: 숫자 문자열 S가 주어질 때, 최소 개수의 여는 괄호와 닫는 괄호를 삽입하여 결과 문자열이 균형잡히고(balanced), 각 숫자 d가 정확히 d쌍의 매칭 괄호 안에 있도록 만들어라.

문자열에서 두 괄호 사이의 중첩(nesting)은 그 둘 사이에 엄격히 포함되는 부분 문자열을 의미한다. 어떤 여는 괄호와 그 오른쪽에 있는 어떤 닫는 괄호는, 그 둘의 중첩이 비어 있거나, 혹은 중첩 안에 있는 모든 괄호가 중첩 안의 다른 괄호와 매칭된다면 서로 매칭된다(match)고 한다. 어떤 위치 p의 중첩 깊이(nesting depth)는, p가 그 매칭 쌍의 중첩 안에 포함되는 매칭 괄호 쌍의 개수이다.

예를 들어 다음 문자열들은 모든 숫자가 자신의 중첩 깊이와 일치한다: 0((2)1), (((3))1(2)), ((((4)))), ((2))((2))(1). 처음 세 문자열은 같은 숫자들이 같은 순서로 들어가는 문자열들 중 길이가 최소이지만, 마지막 문자열은 그렇지 않다. ((22)1)도 숫자 221를 포함하면서 더 짧기 때문이다.

숫자 문자열 S가 주어질 때, 괄호와 숫자로만 이루어진 또 다른 문자열 S'를 찾아라. S'는 다음을 만족해야 한다:

• S'의 모든 괄호는 어떤 다른 괄호와 매칭된다.
• S'에서 모든 괄호를 제거하면 S가 된다.
• S'의 각 숫자는 자신의 중첩 깊이와 같다.
• S'의 길이는 최소이다.