C++로 문자열 형태의 이진 트리에서 k번째 레벨 노드 값의 곱 구하기

데이터가 문자열 형식으로 저장된 트리가 주어졌을 때, 이진 트리의 k번째 레벨에 있는 노드들의 곱을 구하는 문제입니다. 트리의 각 노드는 세 가지 요소로 구성됩니다. 즉, 데이터 부분, 왼쪽 서브트리를 가리키는 왼쪽 포인터, 그리고 오른쪽 서브트리를 가리키는 오른쪽 포인터입니다.

이진 트리의 레벨은 0부터 시작하며, 임의의 양수 'n'까지 확장될 수 있습니다. 따라서 레벨 'k'가 입력으로 주어지면 프로그램은 해당 'k' 레벨에 존재하는 모든 노드 값의 곱을 계산해야 합니다.

문제 이해하기

예를 들어, 아래와 같은 이진 트리에서 k = 2라고 가정해 보겠습니다.

• 레벨 2에 있는 노드: 40, 50, 60
• 곱 = 40 × 50 × 60 = 120,000

입력 예시 1

(1(2(3()())(4()(5()())))(6(7()())(8()())))
K = 1

출력 결과 1

product of nodes at level k = 12

입력 예시 2

(0(5(6()())(4()(9()())))(7(1()())(3()())))
k = 2

출력 결과 2

product of nodes at level k = 72

알고리즘

이 문제는 트리를 실제 자료구조로 변환하지 않고도 문자열 순회만으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 여는 괄호 '('를 만나면 현재 레벨을 1 증가시킵니다.
2. 닫는 괄호 ')'를 만나면 현재 레벨을 1 감소시킵니다.
3. 숫자 문자를 만나면, 현재 레벨이 목표 레벨 k와 일치하는 경우에만 해당 값을 곱셈 결과에 누적합니다.

알고리즘 단계를 정리하면 다음과 같습니다.

Start
Step 1 → k번째 레벨의 노드 곱을 계산하는 함수 선언
   int product(string tree, int k)
      int level = -1 로 초기화
      int product = 1 로 초기화
      int size = tree.length()
      반복문 For i = 0 ~ size 미만
         IF tree[i] == '(' 인 경우
            level++
         ELSE IF tree[i] == ')' 인 경우
            level--
         ELSE
            IF level == k 인 경우
               product *= (tree[i] - '0')
            End
         End
      End
      return product
Step 2 → main() 함수에서
   string tree = "(1(2(3()())(4()(5()())))(6(7()())(8()())))" 선언
   int k = 1 선언
   product(tree, k) 호출
Stop

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
// k번째 레벨의 노드 곱 구하기
int product(string tree, int k){
   int level = -1;
   int product = 1;
   int size = tree.length();
   for (int i = 0; i < size; i++){
      if (tree[i] == '(')
         level++;
      else if (tree[i] == ')')
         level--;
      else{
         if (level == k)
            product *= (tree[i] - '0');
      }
   }
   return product;
}
int main(){
   string tree = "(1(2(3()())(4()(5()())))(6(7()())(8()())))";
   int k = 1;
   cout << "product of nodes at level k = " << product(tree, k);
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

product of nodes at level k = 12

코드 설명 및 시간 복잡도

위 코드에서 (tree[i] - '0') 연산은 문자 형태의 숫자를 실제 정수 값으로 변환하는 역할을 합니다. 예를 들어 문자 '4'의 ASCII 값에서 '0'의 ASCII 값을 빼면 정수 4를 얻을 수 있습니다.

이 알고리즘은 트리 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. 추가적인 공간 사용 없이 상수 공간만 필요하므로 공간 복잡도는 O(1)입니다. 다만, 노드 값이 두 자리 이상일 경우에는 연속된 숫자 문자를 하나의 수로 묶어 처리하는 추가 로직이 필요할 수 있습니다.