[Google Code Jam 2020] Nesting Depth Python Solution

Problem

tl;dr: Given a string of digits S, insert a minimum number of opening and closing parentheses into it such that the resulting string is balanced and each digit d is inside exactly d pairs of matching parentheses.

Let the nesting of two parentheses within a string be the substring that occurs strictly between them. An opening parenthesis and a closing parenthesis that is further to its right are said to match if their nesting is empty, or if every parenthesis in their nesting matches with another parenthesis in their nesting. The nesting depth of a position p is the number of pairs of matching parentheses m such that p is included in the nesting of m.

For example, in the following strings, all digits match their nesting depth: 0((2)1), (((3))1(2)), ((((4)))), ((2))((2))(1). The first three strings have minimum length among those that have the same digits in the same order, but the last one does not since ((22)1) also has the digits 221 and is shorter.

Given a string of digits S, find another string S’, comprised of parentheses and digits, such that:

• all parentheses in S’ match some other parenthesis,
• removing any and all parentheses from S’ results in S,
• each digit in S’ is equal to its nesting depth, and
• S’ is of minimum length.

이 문제는 최소한의 소괄호(parentheses)를 이용하여 주어진 숫자를 감싸는 방법을 맞추는 방법을 찾는 것이다. 예를 들면, ‘221’이 주어졌을 때, ‘((22)1)’와 같이 결과를 만들어 주는 것이다. 자칫 어려워보일 수도 있지만 규칙성을 발견하면 굉장히 쉽게 Greedy한 방법으로 정답을 찾을 수 있다는 것을 발견할 수 있다. 주어진 숫자의 앞뒤로 먼저 ‘0’을 추가로 붙여졌다고 가정하자. 그러면 ‘221’은 ‘02210’이 될 것이다. 벌써 규칙이 보이지 않는가? 이전 숫자와의 차이만큼 클 경우 ‘(’를 더해주고 작을 경우 ‘)’를 더해주면 된다! 이를 파이썬 코드로 나타내면, 아래와 같다.

tc = int(input())
for t in range(tc):
    answer = ‘’
    vector = [int(x) for x in input()] + [0]
    cur = 0
    for num in vector:
        if cur < num:
            answer += ‘(‘ * (num — cur)
        else:
            answer += ‘)’ * (cur — num)
        answer += str(num)
        cur = num
    print(“Case #%d: %s” % (t + 1, answer[:-1]))

위 코드에서는 앞에 0을 더해주는 대신 cur = 0 을 이용하였음을 볼 수 있다. 그리고 마지막 print 할 때 먼저 더해줬던 마지막 0 값을 제외하면 된다.