Python에서 괄호 깊이별 문자 'X' 개수를 계산하는 프로그램

문자열 s가 오직 세 가지 문자인 'X', '(', ')' 로만 구성되어 있다고 가정해 보겠습니다. 이 문자열에는 균형이 맞는 괄호가 포함되어 있으며, 그 사이에 여러 개의 'X'가 존재하고, 괄호는 재귀적으로 중첩될 수도 있습니다. 우리의 목표는 문자열 s에서 가장 얕은 깊이부터 가장 깊은 깊이까지, 각 괄호 깊이별로 'X'가 몇 개 있는지 계산하는 것입니다.

예를 들어, 입력이 s = "(XXX(X(XX))XX)"라고 한다면, 출력은 [5, 1, 2]가 됩니다. 첫 번째 괄호 깊이(가장 바깥쪽)에는 5개, 두 번째 깊이에는 1개, 세 번째 깊이(가장 안쪽)에는 2개의 'X'가 있기 때문입니다.

해결 접근 방법

이 문제는 현재 괄호의 깊이를 추적하면서 문자열을 한 번만 순회하면 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다:

• depth를 -1로 초기화합니다. (괄호를 만나야 첫 번째 깊이 0에 진입합니다)
• out이라는 새로운 리스트를 생성하여 각 깊이별 'X' 개수를 저장합니다.
• 문자열 s의 각 문자 c에 대해 다음을 수행합니다:
  • c가 '(' 와 같다면 depth를 1 증가시킵니다. (더 깊은 곳으로 진입)
  • 그렇지 않고 c가 ')' 와 같다면 depth를 1 감소시킵니다. (바깥쪽으로 빠져나옴)
  • depth가 out의 현재 길이와 같다면, 아직 기록되지 않은 새로운 깊이이므로 out의 끝에 0을 추가합니다.
  • c가 'X'와 같다면 해당 깊이의 카운트인 out[depth]를 1 증가시킵니다.
• 모든 문자를 처리한 후 out을 반환합니다.

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리는 결과 리스트를 위한 공간만 필요합니다.

구현 예제

다음 파이썬 구현을 통해 더 자세히 이해해 보겠습니다:

def solve(s):
    depth = -1
    out = []

    for c in s:
        if c == "(":
            depth += 1
        elif c == ")":
            depth -= 1

        if depth == len(out):
            out.append(0)

        if c == "X":
            out[depth] += 1
    return out

s = "(XXX(X(XX))XX)"
print(solve(s))

입력

"(XXX(X(XX))XX)"

출력

[5, 1, 2]